Twin-width of Planar Graphs; a Short Proof

HLINĚNÝ, Petr. Twin-width of Planar Graphs; a Short Proof. Online. In European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23. Brno, Czech Republic: MUNI Press, 2023, s. 595-600. ISSN 2788-3116. Dostupné z: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-082.

Základní údaje

• Originální název: Twin-width of Planar Graphs; a Short Proof
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant, domácí).
• Vydání: Brno, Czech Republic, European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23, od s. 595-600, 6 s. 2023.
• Nakladatel: MUNI Press

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Česká republika
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: elektronická verze "online"
• Kód RIV: RIV/00216224:14330/23:00131578
• Organizační jednotka: Fakulta informatiky
• ISSN: 2788-3116
• Doi: http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-082
• Klíčová slova anglicky: twin-width; planar graph
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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 coming from a construction by Král‘ and Lamaison [arXiv, September 2022], and an upper bound of by Hliněný and Jedelský [arXiv, October 2022]. The upper bound (currently best) of 7, 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.