On the Queue-Number of Partial Orders

DOI10.1007/978-3-030-92931-2_17MaRDI QIDQ6375809arXivFDO

Authors Stefan Felsner, Torsten Ueckerdt, Kaja Wille

Publication date 23 August 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-92931-2_17

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

cs.DMmath.CO

Abstract: The queue-number of a poset is the queue-number of its cover graph viewed as a directed acyclic graph, i.e., when the vertex order must be a linear extension of the poset. Heath and Pemmaraju conjectured that every poset of width $w$ has queue-number at most $w$. Recently, Alam et al. constructed posets of width $w$ with queue-number $w+1$. Our contribution is a construction of posets with width $w$ with queue-number $Omega(w^2)$. This asymptotically matches the known upper bound.

This page was built for publication: On the Queue-Number of Partial Orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6375809)