Twin-Width of Planar Graphs Is at Most 8, and Some Related Bounds
Petr Hliněný, Jan Jedelský · SIAM Journal on Discrete Mathematics · 2025
Abstract. 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.