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

DOI10.1016/J.DISC.2023.113690zbMATH Open1525.05027arXiv2003.07655MaRDI QIDQ6080147FDOQ6080147

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)

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.

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)

Cites Work

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

Cited In (3)

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

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)