论文标题
k-map图的书籍嵌入
Book Embeddings of k-Map Graphs
论文作者
论文摘要
地图是将球体分为标记为国家或孔的区域。地图图的顶点是地图的国家。当且仅当国家邻近并至少在一个点相遇时，才有优势。对于K-Map图，大多数K国家 /地区都会在某个时候见面。如果可以在每个边缘的最多k交叉处将其绘制在平面中，则图为k平面。图形嵌入的p页面是对顶点的线性排序，并将边缘分配给p页，因此分配给同一页面的边缘没有冲突。页面的最小数量是图表的厚度，也称为堆栈编号或页码。我们表明，每个k-map图都有一本书，嵌入$ 6 \ lfloor k/2 \ rfloor+5 $页面，对于n-vertex图，可以从其地图中以o（kn）时间计算。我们的结果改善了最著名的上限。朝下，显示某些K-Map图需要$ \ lfloor 3k/4 \ rfloor $页面。从传来的角度来看，我们获得了1个平面图的11页的改进的上限，这些图是4-MAP图的子图，以及17页的最佳2平面图。
A map is a partition of the sphere into regions that are labeled as countries or holes. The vertices of a map graph are the countries of a map. There is an edge if and only if the countries are adjacent and meet in at least one point. For a k-map graph, at most k countries meet in a point. A graph is k-planar if it can be drawn in the plane with at most k crossings per edge. A p-page book embedding of a graph is a linear ordering of the vertices and an assignment of the edges to p pages, so that there is no conflict for edges assigned to the same page. The minimum number of pages is the book thickness of a graph, also known as stack number or page number. We show that every k-map graph has a book embedding in $6\lfloor k/2 \rfloor+5$ pages, which, for n-vertex graphs, can be computed in O(kn) time from its map. Our result improves the best known upper bound. Towards a lower bound, it is shown that some k-map graphs need $\lfloor 3k/4 \rfloor$ pages. In passing, we obtain an improved upper bound of eleven pages for 1-planar graphs, which are subgraphs of 4-map graphs, and of 17 pages for optimal 2-planar graphs.
