A Sublinear Bound on the Page Number of Upward Planar Graphs
DOI10.1137/22m1522450zbMath1526.05037arXiv2107.05227OpenAlexW3181610989MaRDI QIDQ6057803
Torsten Ueckerdt, Paul Jungeblut, Laura Merker
Publication date: 26 October 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.05227
Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ordered sets, pagenumbers and planarity
- On the chromatic number of multiple interval graphs and overlap graphs
- Fundamentals of planar ordered sets
- Embedding planar graphs in four pages
- Algorithms for plane representations of acyclic digraphs
- The book thickness of a graph
- Area requirement and symmetry display of planar upward drawings
- The pagenumber of spherical lattices is unbounded
- Planar graphs that need four pages
- Computing upward topological book embeddings of upward planar digraphs
- Book embeddability of series-parallel digraphs
- Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs
- 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
- Implementing a Partitioned 2-Page Book Embedding Testing Algorithm
- On the Page Number of Upward Planar Directed Acyclic Graphs
- Improved bounds for colouring circle graphs
- Upward Book Embeddings of st-Graphs
- Four pages are indeed necessary for planar graphs
- Partial orders of dimension 2
- On the upward book thickness problem: combinatorial and complexity results
- Recognizing DAGs with page-number 2 is NP-complete
This page was built for publication: A Sublinear Bound on the Page Number of Upward Planar Graphs