Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar
share
The structural parameter twin-width was introduced by Bonnet et al. in [FOCS 2020], and already this first paper included an asymptotic argument bounding the twin-width of planar graphs by a non-explicit constant. Quite recently, we have seen first small explicit upper bounds of 183 by Jacob and Pilipczuk [arXiv, January 2022, also WG'22], 583 by Bonnet et al. [arXiv, February 2022], of 37 by Bekos et al. [arXiv, April 2022], and of 9 by the first author [arXiv, June 2022]. We further elaborate on the approach used in the last paper and improve the upper bound to 8. This is already very close to the currently best lower bound of 7 by Král and Lamaison [arXiv, September 2022]. We some of the new ideas, we also significantly simplify the previous proof of the first author [arXiv, August 2022] that the twin-width of bipartite planar graphs is at most 6.
READ FULL TEXT
