论文标题
定向的无环外平面图具有恒定的堆栈编号
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
论文作者
论文摘要
有向无环$ g $的堆叠数是$ g $的拓扑排序和$ k $的最低$ k $，其边缘的颜色是相同的颜色交叉的两个边缘，即沿拓扑订购的两个边缘。我们证明了定向的无环外平面图的堆叠数是由常数界定的，该常数为Heath，Pemmaraju和Trenk对猜想提供了积极答案[Siam J. Computing，1999]。直接的结果，这表明所有向上的外平面图都有恒定的堆栈数，这是Bhore等人的一个问题。 [欧洲。 J. COMB。，2023年]，从而取得了重大进展，该问题源自Nowakowski和Parker [Order，1989]。作为我们的主要工具，我们开发了定向$ h $ - 分区的新颖技术，这可能引起独立的兴趣。我们通过构建一个有针对性的无环2树的家族来补充有针对性的环形外平面图，这些堆栈的堆栈编号是无界的堆栈编号，从而反驳了Nöllenburg和PupyRev的猜想[GD 2023]。
The stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We prove that the stack number of directed acyclic outerplanar graphs is bounded by a constant, which gives a positive answer to a conjecture by Heath, Pemmaraju and Trenk [SIAM J. Computing, 1999]. As an immediate consequence, this shows that all upward outerplanar graphs have constant stack number, answering a question by Bhore et al. [Eur. J. Comb., 2023] and thereby making significant progress towards the problem for general upward planar graphs originating from Nowakowski and Parker [Order, 1989]. As our main tool we develop the novel technique of directed $H$-partitions, which might be of independent interest. We complement the bounded stack number for directed acyclic outerplanar graphs by constructing a family of directed acyclic 2-trees that have unbounded stack number, thereby refuting a conjecture by Nöllenburg and Pupyrev [GD 2023].
