Book embeddings of k-framed graphs and k-map graphs

DOI10.1016/J.DISC.2023.113690MaRDI QIDQ6080147zbMATHFDO

Authors Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou

Publication date 30 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07655

zbMATH Keywords

book embeddings\(h\)-framed graphs\(k\)-map graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.

Recommendations

• Book embeddings of nonplanar graphs with small faces in few pages
• Embedding planar 5-graphs in three pages
• Embedding planar graphs in four pages

Cites work

• scientific article; zbMATH DE number 3492580 (Why is no real title available?)
• scientific article; zbMATH DE number 4128415 (Why is no real title available?)
• scientific article; zbMATH DE number 1305408 (Why is no real title available?)
• scientific article; zbMATH DE number 7525495 (Why is no real title available?)
• A left-first search algorithm for planar graphs
• An annotated bibliography on 1-planarity
• Book embeddings of nonplanar graphs with small faces in few pages
• Bounds For Orthogonal 3-D Graph Drawing
• Characterizing 5-map graphs by 2-fan-crossing graphs
• Characterizing and recognizing 4-map graphs
• Degree constrained book embeddings
• Ein Sechsfarbenproblem auf der Kugel
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar 5-graphs in three pages
• Embedding planar graphs in four pages
• Extension of a theorem of Whitney
• Four pages are indeed necessary for planar graphs
• Genus g Graphs Have Pagenumber O(√g)
• Graph treewidth and geometric thickness parameters
• Graphs with E Edges Have Pagenumber O(√E)
• Halin graphs and the travelling salesman problem
• Hamiltonian circuits in simplicial complexes
• Layered separators in minor-closed graph classes with applications
• Linear-time recognition of map graphs with outerplanar witness
• Map graphs
• On Optimal 2- and 3-Planar Graphs
• Planar embeddings with small and uniform faces
• Planar graphs that need four pages
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Recognizing hole-free 4-map graphs in cubic time
• Sorting Using Networks of Queues and Stacks
• Sparsity. Graphs, structures, and algorithms
• Straight-line grid drawings of 3-connected 1-planar graphs
• Succinct representation of balanced parentheses and static trees
• The book thickness of a graph
• The pagenumber of \(k\)-trees is \(O(k)\)
• Two-page book embeddings of 4-planar graphs
• Upward book embeddings of st-graphs
• Upward partitioned book embeddings

Cited in

(4)

• Quantum graph drawing (best student paper)
• Book embeddings of nonplanar graphs with small faces in few pages
• Graph product structure for \(h\)-framed graphs
• Planar drawings with few slopes of Halin graphs and nested pseudotrees

This page was built for publication: Book embeddings of \(k\)-framed graphs and \(k\)-map graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080147)