Four Pages Are Indeed Necessary for Planar Graphs

Michael A. Bekos, Michael Kaufmann, Fabian Klute, Sergey Pupyrev, Chrysanthi Raftopoulou, Torsten Ueckerdt

Research output: Contribution to journalArticleAcademicpeer-review


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.
Original languageEnglish
Pages (from-to)332-353
Number of pages22
JournalJournal of Computational Geometry
Issue number1
Publication statusPublished - 10 Aug 2020


Dive into the research topics of 'Four Pages Are Indeed Necessary for Planar Graphs'. Together they form a unique fingerprint.

Cite this