TY - JOUR

T1 - Four Pages Are Indeed Necessary for Planar Graphs

AU - Bekos, Michael A.

AU - Kaufmann, Michael

AU - Klute, Fabian

AU - Pupyrev, Sergey

AU - Raftopoulou, Chrysanthi

AU - Ueckerdt, Torsten

PY - 2020/8/10

Y1 - 2020/8/10

N2 - 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. In this paper, we address 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. We settle this problem by constructing planar graphs that require four pages in all of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

AB - 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. In this paper, we address 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. We settle this problem by constructing planar graphs that require four pages in all of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

U2 - 10.20382/jocg.v11i1a12

DO - 10.20382/jocg.v11i1a12

M3 - Article

SN - 1920-180X

VL - 11

SP - 332

EP - 353

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

IS - 1

ER -