Planar graphs that need four pages
From MaRDI portal
Publication:2200923
DOI10.1016/j.jctb.2020.05.008zbMath1448.05055arXiv2005.14111OpenAlexW3099097085MaRDI QIDQ2200923
Publication date: 24 September 2020
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.14111
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (18)
A survey on book-embedding of planar graphs ⋮ Subhamiltonian toroidal graphs ⋮ Stack-number is not bounded by queue-number ⋮ Matching book thickness of generalized Petersen graphs ⋮ Straight-line drawings of 1-planar graphs ⋮ A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Graphs of linear growth have bounded treewidth ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Linear layouts of bipartite planar graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Lazy queue layouts of posets ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ On mixed linear layouts of series-parallel graphs ⋮ On Mixed Linear Layouts of Series-Parallel Graphs ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
Cites Work
- Embedding planar graphs in four pages
- The book thickness of a graph
- Graph treewidth and geometric thickness parameters
- The book thickness of 1-planar graphs is constant
- The Book Embedding Problem from a SAT-Solving Perspective
- The Complexity of Coloring Circular Arcs and Chords
- The pagenumber of genus g graphs is O( g )
- Genus g Graphs Have Pagenumber O(√g)
- The pagenumber of \(k\)-trees is \(O(k)\)
This page was built for publication: Planar graphs that need four pages
