Abstract
Twinwidth is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows us to solve many otherwise hard problems efficiently. Graph classes of bounded twinwidth, in which appropriate contraction sequences are efficiently constructible, are thus of interest in combinatorics and in computer science. However, we currently do not know in general how to obtain a witnessing contraction sequence of low width efficiently, and published upper bounds on the twinwidth in nontrivial cases are often "astronomically large".
We focus on planar graphs, which are known to have bounded twinwidth (already since the introduction of twinwidth), but the first explicit "nonastronomical" upper bounds on the twinwidth of planar graphs appeared just a year ago; namely the bound of 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.), 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twinwidth of every planar graph is at most 8, and construct a witnessing contraction sequence in linear time. Note that the currently best lowerbound planar example is of twinwidth 7, by Král' and Lamaison [arXiv, September 2022]. We also prove that the twinwidth of every bipartite planar graph is at most 6, and again construct a witnessing contraction sequence in linear time.
BibTeX  Entry
@InProceedings{hlineny_et_al:LIPIcs.ICALP.2023.75,
author = {Hlin\v{e}n\'{y}, Petr and Jedelsk\'{y}, Jan},
title = {{TwinWidth of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {75:175:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18127},
URN = {urn:nbn:de:0030drops181271},
doi = {10.4230/LIPIcs.ICALP.2023.75},
annote = {Keywords: twinwidth, planar graph}
}
Keywords: 

twinwidth, planar graph 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 