Four Pages Are Indeed Necessary for Planar Graphs

• Published in 2020
• Added on 2020-04-19

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 demonstrating planar graphs that require four pages in any of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

Links

• http://arxiv.org/abs/2004.07630v1
• http://arxiv.org/pdf/2004.07630v1

Other information

BibTeX entry

@article{FourPagesAreIndeedNecessaryforPlanarGraphs,
	key = {FourPagesAreIndeedNecessaryforPlanarGraphs},
	type = {article},
	title = {Four Pages Are Indeed Necessary for Planar Graphs},
	author = {Michael A. Bekos and Michael Kaufmann and Fabian Klute and Sergey Pupyrev and Chrysanthi Raftopoulou and Torsten Ueckerdt},
	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. 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 demonstrating
planar graphs that require four pages in any of their book embeddings, thus
establishing that the book thickness of the class of planar graphs is four.},
	comment = {},
	date_added = {2020-04-19},
	date_published = {2020-04-10},
	urls = {http://arxiv.org/abs/2004.07630v1,http://arxiv.org/pdf/2004.07630v1},
	collections = {Attention-grabbing titles,Fun maths facts},
	url = {http://arxiv.org/abs/2004.07630v1 http://arxiv.org/pdf/2004.07630v1},
	year = 2020,
	urldate = {2020-04-19},
	archivePrefix = {arXiv},
	eprint = {2004.07630},
	primaryClass = {cs.DS}
}