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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2025

Confidentiality

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

Name of the periodical

SIAM JOURNAL ON DISCRETE MATHEMATICS

ISSN

0895-4801

e-ISSN

—

Volume of the periodical

39

Issue of the periodical within the volume

4

Country of publishing house

DE - GERMANY

Number of pages

46

Pages from-to

2003-2048

UT code for WoS article

001636478100004

EID of the result in the Scopus database

2-s2.0-105023328566