Directed acyclic outerplanar graphs have constant stack number

DOI10.46298/THEORETICS.25.25MaRDI QIDQ6858217zbMATH OpenFDO

Authors Paul Jungeblut, Laura Merker, Torsten Ueckerdt

Publication date 13 February 2026

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.25.25

zbMATH Keywords

2-treesdirected graphslinear layoutsouterplanar graphsstack number

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Cites work

• A left-first search algorithm for planar graphs
• A Sublinear Bound on the Page Number of Upward Planar Graphs
• A Theorem on Planar Graphs
• Book embeddability of series-parallel digraphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Crossing-free acyclic Hamiltonian path completion for planar \(st\)-digraphs
• Directed acyclic outerplanar graphs have constant stack number
• Embedding planar 5-graphs in three pages
• Embedding planar graphs in four pages
• Four pages are indeed necessary for planar graphs
• Genus g Graphs Have Pagenumber O(√g)
• Graph treewidth and geometric thickness parameters
• scientific article; zbMATH DE number 3499787 (Why is no real title available?)
• scientific article; zbMATH DE number 398966 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 219264 (Why is no real title available?)
• Improved bounds for colouring circle graphs
• Improved bounds for track numbers of planar graphs
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Linear layouts of bipartite planar graphs
• Linear layouts of complete graphs
• Mixed linear layouts of planar graphs
• Mixed linear layouts: complexity, heuristics, and experiments
• On dispersable book embeddings
• On families of planar DAGs with constant stack number
• On mixed linear layouts of series-parallel graphs
• On the book embedding of ordered sets.
• On the chromatic number of multiple interval graphs and overlap graphs
• On the page number of upward planar directed acyclic graphs
• On the pagenumber of \(k\)-trees
• On the upward book thickness problem: combinatorial and complexity results
• Ordered sets, pagenumbers and planarity
• Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
• Planar graphs have bounded queue-number
• Planar graphs that need four pages
• Plane Drawings of Queue and Deque Graphs
• Recognizing DAGs with page-number 2 is NP-complete
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Stack and Queue Layouts of Posets
• Stack and queue number of 2-trees
• Star arboricity of graphs
• The book thickness of a graph
• The Local Queue Number of Graphs with Bounded Treewidth
• The mixed page number of graphs
• The pagenumber of k-trees is O(k)
• The pagenumber of spherical lattices is unbounded
• The Rique-number of graphs
• Track layouts, layered path decompositions, and leveled planarity
• Two-page book embeddings of 4-planar graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms

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 Q6858217)