Twin-width of Planar Graphs; a Short Proof

EUROCOMB’23

Abstract
The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from a final resolution; there is a lower bound of $7$ coming from a construction by Král‘ and Lamaison [arXiv, September 2022], and an upper bound of $8$ by Hliněný and Jedelský [arXiv, October 2022]. The upper bound (currently best) of $8$, however, is rather complicated and involved. We give a short and simple self-contained proof that the twin-width of planar graphs is at most $11$.

Pages:
595–600
References

Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph product structure for h-framed graphs. CoRR, abs/2204.11495v1, 2022. arXiv:2204.11495v1.

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):3:1-3:46, 2022.
https://doi.org/10.1145/3486655

Édouard Bonnet, O-joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR, abs/2202.11858, 2022. arXiv:2202.11858.

Petr Hliněný. Twin-width of planar graphs is at most 9, and at most 6 when bipartite planar. CoRR, abs/2205.05378, 2022. arXiv:2205.05378.

Petr Hliněný and Jan Jedelský. Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. CoRR, abs/2210.08620, 2022. Accepted to ICALP 2023. arXiv:2210.08620.

Hugo Jacob and Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In WG, volume 13453 of Lecture Notes in Computer Science, pages 287-299. Springer, 2022.
https://doi.org/10.1007/978-3-031-15914-5_21

Daniel Král and Ander Lamaison. Planar graph with twin-width seven. abs/2209.11537, 2022. arXiv:2209.11537.
https://doi.org/10.1016/j.ejc.2023.103749

Metrics

0

Views

0

PDF views