Directed Acyclic Outerplanar Graphs Have Constant Stack Number

DOI10.1109/FOCS57990.2023.00118arXiv2211.04732MaRDI QIDQ6507002FDOQ6507002

Authors: Paul Jungeblut, Laura Merker, Torsten Ueckerdt 

Abstract: 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"ollenburg and Pupyrev [arXiv:2107.13658, 2021].

This page was built for publication: Directed Acyclic Outerplanar Graphs Have Constant Stack Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507002)