论文标题
二维Posets的队列布局
Queue Layouts of Two-Dimensional Posets
论文作者
论文摘要
当顶点顺序是poset的线性扩展时，poset的队列号是其盖子图的队列编号。 Heath和Pemmaraju猜想，每个宽度$ W $的poset最多都有$ w $。猜想已被确认为宽度$ w = 2 $的POSET，以及$ 0 $和$ 1 $的Planar Posets。相比之下，猜想被宽度$ W> 2 $的一般（非平面）posets拒绝。 在本文中，我们研究了二维POSET的队列布局。首先，我们构建了宽度$ w> 2 $的二维poset，队列编号$ 2（w-1）$，从而反驳了二维POSETS的猜想。其次，我们在此类posets的队列号上显示$ W（W+1）/2 $的上限，从而改善了每$ W> 3 $的$（W-1）^2+1 $的先前最著名的界限。
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$.
