Abstract
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:138, 2020].
In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the hframed graphs, a graph class that includes 1planar, optimal 2planar, and kmap graphs (for appropriate values of h). We establish a graph product structure theorem for hframed 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⌊ h/2 ⌋+⌊ h/3 ⌋1. This allows us to improve over the previous structural theorems for 1planar and kmap graphs. Our results constitute significant progress over the previous bounds on the queue number, nonrepetitive chromatic number, and pcentered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1planar graphs and kmap graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ 3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twinwidth of 1planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
BibTeX  Entry
@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23,
author = {Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael},
title = {{Graph Product Structure for hFramed Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {23:123:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17308},
URN = {urn:nbn:de:0030drops173086},
doi = {10.4230/LIPIcs.ISAAC.2022.23},
annote = {Keywords: Graph product structure theory, hframed graphs, kmap graphs, queue number, twinwidth}
}
Keywords: 

Graph product structure theory, hframed graphs, kmap graphs, queue number, twinwidth 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 