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\'c 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.
翻译:图形结构结构的理论表示某些图表, 作为更简单图形的强产物的子图。 特别是, 我们使用一个优雅的公式来寻找这个强大的工具的扩展, 特别是, 一个路径和一个捆绑的树形图的强烈产物, 并且可以将一个捆绑的树形图的组合结果提升到产品结构所持有的图表类, 例如 平板图 [Dujmovi\c'c 等人, J. ACM, 67(4), 22:1- 38, 2020] 。 在本文中, 我们共同寻找这个强大的工具的扩展, 包括一个路径和一个连接的树形图的精度, 包括一个路径的精度, 一个路径的精度的精度, 平面图的精度, 直径从一个直径的平面图到一个直径直的平面图数, 最深处的平面的图数从一个直径直径直到一个直径直径直的平面的平面的平面图数, 从一个直径直径直到一个直径直径直的平面的平面的平面的平面的平面图, 。