Directed Acyclic Outerplanar Graphs Have Constant Stack Number

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. [GD 2021] 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].

Authors

• Paul Jungeblut
• Laura Merker
• Torsten Ueckerdt

Keywords

• Heating systems
• Computer science
• Directed acyclic graph
• Color
• Constant Number
• Outerplanar Graphs
• Conjecture
• Acyclic Graph
• Immediate Consequence
• Topological States
• Planar Graphs
• Upper Bound
• Related Concepts
• Directed Graph
• Maximum Degree
• Non-planar
• Single Edge
• Important Open Question
• Left Child
• Ordering Of The Vertices