License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.16
URN: urn:nbn:de:0030-drops-121749
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12174/
Go to the corresponding LIPIcs Volume Portal


Bekos, Michael A. ; Da Lozzo, Giordano ; Griesbach, Svenja M. ; Gronemann, Martin ; Montecchiani, Fabrizio ; Raftopoulou, Chrysanthi

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

pdf-format:
LIPIcs-SoCG-2020-16.pdf (1.0 MB)


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 and all optimal 2-planar 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 graphs.

BibTeX - Entry

@InProceedings{bekos_et_al:LIPIcs:2020:12174,
  author =	{Michael A. Bekos and Giordano Da Lozzo and Svenja M. Griesbach and Martin Gronemann and Fabrizio Montecchiani and Chrysanthi Raftopoulou},
  title =	{{Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12174},
  URN =		{urn:nbn:de:0030-drops-121749},
  doi =		{10.4230/LIPIcs.SoCG.2020.16},
  annote =	{Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton}
}

Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI