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

J 2025

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

HLINĚNÝ, Petr a Jan JEDELSKÝ

Základní údaje

Originální název

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

Autoři

HLINĚNÝ, Petr a Jan JEDELSKÝ

Vydání

SIAM JOURNAL ON DISCRETE MATHEMATICS, UNITED STATES, SIAM PUBLICATIONS, 2025, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Německo

Utajení

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

Odkazy

arXiv

Impakt faktor

Impact factor: 1.000 v roce 2024

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00144019

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

twin-width; planar graph; 1-planar graph; map graph

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 2. 4. 2026 13:46, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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á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

HLINĚNÝ, Petr a Jan JEDELSKÝ. Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds. SIAM JOURNAL ON DISCRETE MATHEMATICS. UNITED STATES: SIAM PUBLICATIONS, 2025, roč. 39, č. 4, s. 2003-2048. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/23M1623823.

@article{2561801,
   author = {Hliněný, Petr and Jedelský, Jan},
   article_location = {UNITED STATES},
   article_number = {4},
   doi = {https://doi.org/10.1137/23M1623823},
   keywords = {twin-width; planar graph; 1-planar graph; map graph},
   language = {eng},
   issn = {0895-4801},
   journal = {SIAM JOURNAL ON DISCRETE MATHEMATICS},
   title = {Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds},
   url = {http://arxiv.org/abs/2210.08620},
   volume = {39},
   year = {2025}
}

TY  - JOUR
ID  - 2561801
AU  - Hliněný, Petr - Jedelský, Jan
PY  - 2025
TI  - Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds
JF  - SIAM JOURNAL ON DISCRETE MATHEMATICS
VL  - 39
IS  - 4
SP  - 2003-2048
EP  - 2003-2048
PB  - SIAM PUBLICATIONS
SN  - 08954801
KW  - twin-width
KW  - planar graph
KW  - 1-planar graph
KW  - map graph
UR  - http://arxiv.org/abs/2210.08620
N2  - 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.
ER  -

HLINĚNÝ, Petr a Jan JEDELSKÝ. Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds. \textit{SIAM JOURNAL ON DISCRETE MATHEMATICS}. UNITED STATES: SIAM PUBLICATIONS, 2025, roč.~39, č.~4, s.~2003-2048. ISSN~0895-4801. Dostupné z: https://doi.org/10.1137/23M1623823.

Přehled o publikaci