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, namely to k-map graphs. In fact, our technique can deal with any nonplanar graph having a biconnected skeleton of crossing-free edges whose faces have bounded degree. We prove that this family of graphs has book thickness bounded in k, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.

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

Montecchiani F.
;
2024

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, namely to k-map graphs. In fact, our technique can deal with any nonplanar graph having a biconnected skeleton of crossing-free edges whose faces have bounded degree. We prove that this family of graphs has book thickness bounded in k, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.
2024
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1569360
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact