On the Queue-Number of Partial Orders

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.

Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)