On the Queue-Number of Partial Orders

DOI10.1007/978-3-030-92931-2_17arXiv2108.09994MaRDI QIDQ6375809FDOQ6375809

Torsten Ueckerdt, Stefan Felsner, Kaja Wille

Publication date: 23 August 2021

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.

Mathematics Subject Classification ID

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

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)