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, p. 595-600. ISSN 2788-3116. Available from: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-082.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Twin-width of Planar Graphs; a Short Proof
Authors HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution).
Edition Brno, Czech Republic, European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23, p. 595-600, 6 pp. 2023.
Publisher MUNI Press
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Czech Republic
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/23:00131578
Organization unit Faculty of Informatics
ISSN 2788-3116
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-082
Keywords in English twin-width; planar graph
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Changed: 4/9/2023 09:35.
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 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.
PrintDisplayed: 15/6/2024 16:30