English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The stack number of a directed acyclic graph $G$ is the minimum $k$ for whichthere is a topological ordering of $G$ and a $k$-coloring of the edges suchthat no two edges of the same color cross, i.e., have alternating endpointsalong the topological ordering. We prove that the stack number of directedacyclic outerplanar graphs is bounded by a constant, which gives a positiveanswer to a conjecture by Heath, Pemmaraju and Trenk [SIAM J. Computing, 1999].As an immediate consequence, this shows that all upward outerplanar graphs haveconstant stack number, answering a question by Bhore et al. [GD 2021] andthereby making significant progress towards the problem for general upwardplanar graphs originating from Nowakowski and Parker [Order, 1989]. As our maintool we develop the novel technique of directed $H$-partitions, which might beof independent interest. We complement the bounded stack number for directedacyclic outerplanar graphs by constructing a family of directed acyclic 2-treesthat have unbounded stack number, thereby refuting a conjecture by N\"ollenburgand Pupyrev [arXiv:2107.13658, 2021].

Directed Acyclic Outerplanar Graphs Have Constant Stack Number