Heath, Pemmaraju and Trenk's bounded stack-number conjecture for outerplanar DAGs

Let GG be a directed acyclic outerplanar graph, and let sn(G)\operatorname{sn}(G) 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 GG satisfies sn(G)24776\operatorname{sn}(G) \leq 24776.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.