Queue Layouts of Two-Dimensional Posets

Abstract

The queue number of a poset is the queue number of its cover graph when the vertex order is a linear extension of the poset. Heath and Pemmaraju conjectured that every poset of width $w$ has queue number at most $w$. The conjecture has been confirmed for posets of width $w=2$ and for planar posets with $0$ and $1$. In contrast, the conjecture has been refused by a family of general (non-planar) posets of width $w>2$. In this paper, we study queue layouts of two-dimensional posets. First, we construct a two-dimensional poset of width $w>2$ with queue number $2(w-1)$, thereby disproving the conjecture for two-dimensional posets. Second, we show an upper bound of $w(w+1)/2$ on the queue number of such posets, thus improving the previously best-known bound of $(w-1{)}^2+1$ for every $w>3$.

arXiv commentAppears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)