Graph Product Structure for h-Framed Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139110" target="_blank" >RIV/00216224:14330/24:00139110 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i4p56" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i4p56</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/12123" target="_blank" >10.37236/12123</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Graph Product Structure for h-Framed Graphs

Popis výsledku v původním jazyce

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 lead to 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 72. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

Název v anglickém jazyce

Graph Product Structure for h-Framed Graphs

Popis výsledku anglicky

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 lead to 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 72. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ELECTRONIC JOURNAL OF COMBINATORICS

ISSN

1077-8926

e-ISSN

1077-8926

Svazek periodika

31

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

„P4.56“

Kód UT WoS článku

001367413400001

EID výsledku v databázi Scopus

2-s2.0-85211233237