Planar graphs that need four pages

DOI10.1016/J.JCTB.2020.05.008MaRDI QIDQ2200923zbMATH OpenOpenAlexFDO

Authors Mihalis Yannakakis

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

zbMATH Keywords

book thicknessplanar graphsbook embeddingpagenumber

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We show that there are planar graphs that require four pages in any book embedding.

Cites work

• Embedding planar graphs in four pages
• Genus g Graphs Have Pagenumber O(√g)
• Graph treewidth and geometric thickness parameters
• The Complexity of Coloring Circular Arcs and Chords
• The book embedding problem from a SAT-solving perspective
• The book thickness of a graph
• The pagenumber of \(k\)-trees is \(O(k)\)
• The pagenumber of genus g graphs is O( g )

Cited in

(19)

• On the upward book thickness problem: combinatorial and complexity results
• On 3-coloring circle graphs
• A survey on book-embedding of planar graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
• Graphs of linear growth have bounded treewidth
• On mixed linear layouts of series-parallel graphs
• On Mixed Linear Layouts of Series-Parallel Graphs
• Stack-number is not bounded by queue-number
• Recognizing DAGs with page-number 2 is NP-complete
• Linear layouts of bipartite planar graphs
• Matching book thickness of generalized Petersen graphs
• A Sublinear Bound on the Page Number of Upward Planar Graphs
• Treewidth, Circle Graphs, and Circular Drawings
• Recognizing DAGs with page-number 2 is NP-complete
• Subhamiltonian toroidal graphs
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Straight-line drawings of 1-planar graphs
• Lazy queue layouts of posets

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)