Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00144019" target="_blank" >RIV/00216224:14330/25:00144019 - isvavai.cz</a>

Výsledek na webu

<a href="http://arxiv.org/abs/2210.08620" target="_blank" >http://arxiv.org/abs/2210.08620</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/23M1623823" target="_blank" >10.1137/23M1623823</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds

Popis výsledku v původním jazyce

Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020] and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference in the neighborhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. While for many natural graph classes, it is known that their twin-width is bounded, and published upper bounds on the twin-width in nontrivial cases are very often "astronomically large," We focus on planar graphs, which are known to already have bounded twin-width since its introduction, but it took some time for the first explicit "nonastronomical" upper bounds to come. Namely, in the order of preprint appearance, the bound was at most 183 by Jacob and Pilipczuk [arXiv, January 2022], and 583 by Bonnet, Kwon and Wood [arXiv, February 2022]. Subsequent arXiv manuscripts in 2022 improved the bound down to 37 (Bekos et al.) and 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twin-width of every planar graph is at most 8 and construct a witnessing contraction sequence in linear time. Note that the currently best lower-bound planar example is of twin-width 7 by Král' and Lamaison [arXiv, September 2022]. We also prove small explicit upper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and 16) and of map graphs (38). The common denominator of all these results is the use of a novel specially crafted recursive decomposition of planar graphs, which may be found useful also in other areas.

Název v anglickém jazyce

Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds

Popis výsledku anglicky

Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020] and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference in the neighborhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. While for many natural graph classes, it is known that their twin-width is bounded, and published upper bounds on the twin-width in nontrivial cases are very often "astronomically large," We focus on planar graphs, which are known to already have bounded twin-width since its introduction, but it took some time for the first explicit "nonastronomical" upper bounds to come. Namely, in the order of preprint appearance, the bound was at most 183 by Jacob and Pilipczuk [arXiv, January 2022], and 583 by Bonnet, Kwon and Wood [arXiv, February 2022]. Subsequent arXiv manuscripts in 2022 improved the bound down to 37 (Bekos et al.) and 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twin-width of every planar graph is at most 8 and construct a witnessing contraction sequence in linear time. Note that the currently best lower-bound planar example is of twin-width 7 by Král' and Lamaison [arXiv, September 2022]. We also prove small explicit upper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and 16) and of map graphs (38). The common denominator of all these results is the use of a novel specially crafted recursive decomposition of planar graphs, which may be found useful also in other areas.

Druh

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

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

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>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

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

SIAM JOURNAL ON DISCRETE MATHEMATICS

ISSN

0895-4801

e-ISSN

—

Svazek periodika

39

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

46

Strana od-do

2003-2048

Kód UT WoS článku

001636478100004

EID výsledku v databázi Scopus

2-s2.0-105023328566