Heath, Pemmaraju and Trenk's bounded stack-number conjecture for outerplanar DAGs
Heath, Pemmaraju and Trenk's bounded stack-number conjecture for outerplanar DAGs
Let be a directed acyclic outerplanar graph, and let denote its stack number. Heath, Pemmaraju and Trenk's conjecture. The stack number of the class of directed acyclic outerplanar graphs is bounded above by a constant.
This was a long-standing question concerning whether stack number is bounded for outerplanar directed acyclic graphs. The present paper proves the conjecture, in fact showing that every outerplanar DAG satisfies .
Sources & referencesView supporting material
Primary source
Paul Jungeblut, Laura Merker and Torsten Ueckerdt, “Directed Acyclic Outerplanar Graphs Have Constant Stack Number”, arXiv:2211.04732 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.