Graph Product Structure for h-Framed Graphs

D 2022

Graph Product Structure for h-Framed Graphs

BEKOS, Michael A., Giordano DA LOZZO, Petr HLINĚNÝ a Michael KAUFMANN

Základní údaje

Originální název

Graph Product Structure for h-Framed Graphs

Autoři

BEKOS, Michael A. (300 Řecko), Giordano DA LOZZO (380 Itálie), Petr HLINĚNÝ (203 Česká republika, garant, domácí) a Michael KAUFMANN (276 Německo)

Vydání

LIPIcs 248. Dagstuhl, Germany, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), od s. "23:1"-"23:15", 15 s. 2022

Nakladatel

Schloss Dagstuhl

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

DOI open access

Kód RIV

RIV/00216224:14330/22:00129307

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-258-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.23

Klíčová slova anglicky

Graph product structure theory; h-framed graphs; k-map graphs; queue number; twin-width

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 3. 2023 12:07, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

GA20-04567S, projekt VaV

Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

Citovat

BEKOS, Michael A., Giordano DA LOZZO, Petr HLINĚNÝ a Michael KAUFMANN. Graph Product Structure for h-Framed Graphs. Online. In Bae, Sang Won and Park, Heejin. 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs 248. Dagstuhl, Germany: Schloss Dagstuhl, 2022, s. "23:1"-"23:15", 15 s. ISBN 978-3-95977-258-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.23.

@inproceedings{2244009,
   author = {Bekos, Michael A. and Da Lozzo, Giordano and Hliněný, Petr and Kaufmann, Michael},
   address = {Dagstuhl, Germany},
   booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.23},
   edition = {LIPIcs 248},
   editor = {Bae, Sang Won and Park, Heejin},
   keywords = {Graph product structure theory; h-framed graphs; k-map graphs; queue number; twin-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-258-7},
   pages = {"23:1"-"23:15"},
   publisher = {Schloss Dagstuhl},
   title = {Graph Product Structure for h-Framed Graphs},
   url = {https://doi.org/10.4230/LIPIcs.ISAAC.2022.23},
   year = {2022}
}

TY  - JOUR
ID  - 2244009
AU  - Bekos, Michael A. - Da Lozzo, Giordano - Hliněný, Petr - Kaufmann, Michael
PY  - 2022
TI  - Graph Product Structure for h-Framed Graphs
PB  - Schloss Dagstuhl
CY  - Dagstuhl, Germany
SN  - 9783959772587
KW  - Graph product structure theory
KW  - h-framed graphs
KW  - k-map graphs
KW  - queue number
KW  - twin-width
UR  - https://doi.org/10.4230/LIPIcs.ISAAC.2022.23
N2  - 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.
ER  -

BEKOS, Michael A., Giordano DA LOZZO, Petr HLINĚNÝ a Michael KAUFMANN. Graph Product Structure for h-Framed Graphs. Online. In Bae, Sang Won and Park, Heejin. \textit{33rd International Symposium on Algorithms and Computation (ISAAC 2022)}. LIPIcs 248. Dagstuhl, Germany: Schloss Dagstuhl, 2022, s.~''23:1''-''23:15'', 15 s. ISBN~978-3-95977-258-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.23.

Podrobný výpis o publikaci