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 embeddingbook thicknesspagenumberplanar graphs

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 book embedding problem from a SAT-solving perspective
• The book thickness of a graph
• The Complexity of Coloring Circular Arcs and Chords
• The pagenumber of k-trees is O(k)
• The pagenumber of genus g graphs is O( g )

Cited in

(27)

• On mixed linear layouts of series-parallel graphs
• Augmenting a tree to a k-arbor-connected graph with pagenumber k
• A survey on book-embedding of planar graphs
• Subhamiltonian toroidal graphs
• Stack-number is not bounded by queue-number
• Recognizing DAGs with page-number 2 is NP-complete
• Lazy queue layouts of posets
• On Mixed Linear Layouts of Series-Parallel Graphs
• Matching book thickness of generalized Petersen graphs
• On the upward book thickness problem: combinatorial and complexity results
• 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
• On 3-coloring circle graphs
• On the stack layouts of toroidal grids
• Directed acyclic outerplanar graphs have constant stack number
• On the page-number of a circulant graph
• On the pagenumber of 1-planar graphs
• Automated rendering of multi-stranded DNA complexes with pseudoknots
• Forbidden patterns in mixed linear layouts
• Linear layouts of graphs with priority queues
• The page number of monotone directed acyclic outerplanar graphs is four or five

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)