Planar graphs that need four pages
From MaRDI portal
Publication:2200923
DOI10.1016/J.JCTB.2020.05.008zbMATH Open1448.05055arXiv2005.14111OpenAlexW3099097085MaRDI QIDQ2200923FDOQ2200923
Authors: Mihalis Yannakakis 
Publication date: 24 September 2020
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We show that there are planar graphs that require four pages in any book embedding.
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)
Cites Work
- The Complexity of Coloring Circular Arcs and Chords
- The book thickness of a graph
- Embedding planar graphs in four pages
- Graph treewidth and geometric thickness parameters
- Genus g Graphs Have Pagenumber O(√g)
- The pagenumber of \(k\)-trees is \(O(k)\)
- The pagenumber of genus g graphs is O( g )
- The book embedding problem from a SAT-solving perspective
Cited In (19)
- On Mixed Linear Layouts of Series-Parallel Graphs
- Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
- Lazy queue layouts of posets
- On the upward book thickness problem: combinatorial and complexity results
- Straight-line drawings of 1-planar graphs
- Subhamiltonian toroidal graphs
- A survey on book-embedding of planar graphs
- Linear layouts of bipartite planar graphs
- A Sublinear Bound on the Page Number of Upward Planar Graphs
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- Stack-number is not bounded by queue-number
- Treewidth, Circle Graphs, and Circular Drawings
- Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
- On 3-coloring circle graphs
- Recognizing DAGs with page-number 2 is NP-complete
- Recognizing DAGs with page-number 2 is NP-complete
- Graphs of linear growth have bounded treewidth
- On mixed linear layouts of series-parallel graphs
- Matching book thickness of generalized Petersen graphs
This page was built for publication: Planar graphs that need four pages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200923)
