Four Pages Are Indeed Necessary for Planar Graphs
Fabian Klute
Date: 16:00 – 16:30, Thursday, 29.10.2020
Location: Teams ICS Colloquium
Title: Four Pages Are Indeed Necessary for Planar Graphs
Abstract: An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of 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. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. Book embeddings have been widely studied by researchers in discrete mathematics, graph theory, and graph drawing since the 1960s. The results find applications in areas like traffic control, visualization, or RNA folding.
In this talk I present a recent result resolving a long-standing open problem regarding the exact book thickness of the class of planar graphs, which previously was known to be either three or four. I will present a family of planar graphs that requires four pages in all of its book embeddings. Before introducing the construction an overview of the area and known results, including a short introduction on how to embed planar graphs in few pages, will be given.
Joint research with Michael Kaufmann, Michael A. Bekos, Sergey Pupyrev, Chrysanthi N. Raftopoulou, and Torsten Ueckerdt.