论文标题
H框架图的图形结构
Graph Product Structure for h-Framed Graphs
论文作者
论文摘要
图产品结构理论将某些图表示为更简单图的强产物的子图。特别是，针对相应的结构定理的优雅配方涉及路径和有界树宽图的强产物，并允许将有界树宽图的组合结果提升到图形类别的图形类别，例如平面图[Dujmović等，J.Acm，67（J.Acm，67（4）（4），22：1-1-38，202020202020。 在本文中，我们通过考虑H-Framed Graphs，包括1平面，最佳2平面和K-Map图（用于H）（用于适当的H），将其超越平面的扩展搜索。我们为H框图建立了图形产物结构定理，表明此类中的图是路径强产物的子图，最多3个平面图的平面图，以及一个大小$ 3 \ lfloor h/2 \ lfloor h/2 \ rfloor +rfloor +\ rfloor +\ lfloor H/3 \ rfloor -rfloor -1 $。这使我们可以改进1平面和K-MAP图的先前结构定理。我们的结果构成了先前的界限，在队列数，非重复的色度和这些图形类别的p中心数字上，我们将目前最佳的上限降低了1-平面图的队列数量和k-map图的队列数量，从495到81到81，并从495到81到32225k（k-3（k-3）至61k）。我们还采用了产品结构机械来改善平面和1个平面图的当前上限，分别从183到37，从O（1）到80。我们所有的结构结果都是建设性和产生有效算法以获得相应分解的。
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size $3\lfloor h/2 \rfloor +\lfloor h/3 \rfloor -1$. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 495 to 81 and from 32225k(k-3) to 61k, respectively. We also employ the product structure machinery to improve the current upper bounds of twin-width of planar and 1-planar graphs from 183 to 37, and from O(1) to 80, respectively. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
