Document Open Access Logo

Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar

Authors Petr Hliněný , Jan Jedelský

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.75.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Author Details

Petr Hliněný
  • Masaryk University, Brno, Czech republic
Jan Jedelský
  • Masaryk University, Brno, Czech republic

Funding

Jan Jedelský was partially supported by Masaryk University project MUNI/I/1677/2018.

Cite As Get BibTex

Petr Hliněný and Jan Jedelský. Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.75

Abstract

Twin-width 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 twin-width, 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 twin-width in non-trivial cases are often "astronomically large".
We focus on planar graphs, which are known to have bounded twin-width (already since the introduction of twin-width), but the first explicit "non-astronomical" upper bounds on the twin-width 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 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 that the twin-width of every bipartite planar graph is at most 6, and again construct a witnessing contraction sequence in linear time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • twin-width
  • planar graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jungho Ahn, Kevin Hendrey, Donggyu Kim, and Sang-il Oum. Bounds for the twin-width of graphs. CoRR, abs/2110.03957, 2021. URL: https://arxiv.org/abs/2110.03957.
  2. Jakub Balabán and Petr Hliněný. Twin-width is linear in the poset width. In IPEC, volume 214 of LIPIcs, pages 6:1-6:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  3. Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph product structure for h-framed graphs. CoRR, abs/2204.11495v1, 2022. URL: https://arxiv.org/abs/2204.11495v1.
  4. Pierre Bergé, Édouard Bonnet, and Hugues Déprés. Deciding twin-width at most 4 is NP-complete. In ICALP, volume 229 of LIPIcs, pages 18:1-18:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  5. Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. Twin-width VIII: delineation and win-wins. In IPEC, volume 249 of LIPIcs, pages 9:1-9:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  6. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In SODA, pages 1977-1996. SIAM, 2021. Google Scholar
  7. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. In ICALP, volume 198 of LIPIcs, pages 35:1-35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  8. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk. Twin-width IV: ordered graphs and matrices. In STOC, pages 924-937. ACM, 2022. Google Scholar
  9. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, and Stéphan Thomassé. Twin-width VI: the lens of contraction sequences. In SODA, pages 1036-1056. SIAM, 2022. Google Scholar
  10. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In FOCS, pages 601-612. IEEE, 2020. Google Scholar
  11. É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. Google Scholar
  12. É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. URL: https://arxiv.org/abs/2202.11858.
  13. Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. Twin-width and permutations. CoRR, abs/2102.06880, 2021. URL: https://arxiv.org/abs/2102.06880.
  14. Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM, 67(4):22:1-22:38, 2020. URL: https://doi.org/10.1145/3385731.
  15. Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, and Szymon Torunczyk. Twin-width and types. In ICALP, volume 229 of LIPIcs, pages 123:1-123:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  16. Petr Hliněný. Twin-width of planar graphs is at most 9, and at most 6 when bipartite planar. CoRR, abs/2205.05378, 2022. URL: https://arxiv.org/abs/2205.05378.
  17. 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. URL: https://arxiv.org/abs/2210.08620.
  18. 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. Google Scholar
  19. Daniel Král and Ander Lamaison. Planar graph with twin-width seven. CoRR, abs/2209.11537, 2022. URL: https://arxiv.org/abs/2209.11537.
  20. Michal Pilipczuk, Marek Sokolowski, and Anna Zych-Pawlewicz. Compact representation for matrices of bounded twin-width. In STACS, volume 219 of LIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  21. Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. CoRR, abs/2108.00198, 2021. URL: https://arxiv.org/abs/2108.00198.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact