Detailed Information on Publication Record
2022
Graph Product Structure for h-Framed Graphs
BEKOS, Michael A., Giordano DA LOZZO, Petr HLINĚNÝ and Michael KAUFMANNBasic information
Original name
Graph Product Structure for h-Framed Graphs
Authors
BEKOS, Michael A. (300 Greece), Giordano DA LOZZO (380 Italy), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Michael KAUFMANN (276 Germany)
Edition
LIPIcs 248. Dagstuhl, Germany, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), p. "23:1"-"23:15", 15 pp. 2022
Publisher
Schloss Dagstuhl
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
electronic version available online
References:
RIV identification code
RIV/00216224:14330/22:00129307
Organization unit
Faculty of Informatics
ISBN
978-3-95977-258-7
ISSN
Keywords in English
Graph product structure theory; h-framed graphs; k-map graphs; queue number; twin-width
Tags
Tags
International impact, Reviewed
Změněno: 28/3/2023 12:07, RNDr. Pavel Šmerk, Ph.D.
Abstract
V originále
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⌊ h/2 ⌋+⌊ h/3 ⌋-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 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 twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
Links
| GA20-04567S, research and development project |
|