Publication details
Twin-width of Planar Graphs; a Short Proof
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Article in Periodical |
| Magazine / Source | EUROPEAN JOURNAL OF COMBINATORICS |
| MU Faculty or unit | |
| Citation | |
| web | arXiv preprint |
| Doi | https://doi.org/10.1016/j.ejc.2024.104036 |
| Keywords | twin-width; planar graph |
| Description | The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction by Král’ and Lamaison (2022), and an upper bound of 8 by Hliněný and Jedelský (2022). The upper bound (currently best) of 8, however, is rather complicated and involved. In the paper we give a short and simple self-contained proof that the twin-width of planar graphs is at most 11. We believe that this short proof can also shed more light on the topic of upper bound(s) on the twin-width of planar and beyond-planar graphs in general. |