论文标题
对于平面图确实需要四页
Four Pages Are Indeed Necessary for Planar Graphs
论文作者
论文摘要
图中图中的嵌入由书本的脊柱线性顺序组成，并将其边缘分配到本书的页面上，因此在同一页面上没有两个边缘。图表的厚度是其所有书籍嵌入中最少的页面数量。因此，一类图表的书厚度是其所有成员的最大书籍厚度。在本文中，我们解决了关于平面图类别的确切书籍厚度的一个长期开放问题，以前众所周知，这是三个或四个。我们通过演示在其任何书籍嵌入中需要四页的平面图来解决这个问题，从而确定平面图类别的书籍厚度为四个。
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.
