论文标题
在几页的书中嵌入非平面图的嵌入
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
论文作者
论文摘要
一本书中的图形嵌入书，称为书籍嵌入，由沿书脊柱的顶点进行线性顺序，并将其边缘分配到书页面上，因此同一页面上没有两个边缘。图表的厚度是其所有书籍嵌入中最少的页面数量。对于平面图，Yannakakis造成了一个基本的结果，Yannakakis提出了一种算法来计算具有四页的书籍中平面图的嵌入。我们的主要贡献是一种将此结果推广到更广泛的非平面图系列的技术，其特征是无交叉边缘的双连接骨架，其面部的脸部有界限。值得注意的是，该家族包括所有1个平面，所有最佳的2平面和所有K-MAP（带有界限k）图作为子图。我们证明，这个图的家族具有有限的书籍厚度，作为推论，我们获得了最佳2平面和k-Map图的书籍厚度的第一个常数上限。
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and 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. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.
