Twin-width of Planar Graphs is at most 8, and at most 6 when
Bipartite Planar

D 2023

Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar

HLINĚNÝ, Petr and Jan JEDELSKÝ

Basic information

Original name

Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Jan JEDELSKÝ (203 Czech Republic, belonging to the institution)

Edition

Dagstuhl, Germany, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), p. "75:1"-"75:18", 18 pp. 2023

Publisher

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/23:00131119

Organization unit

Faculty of Informatics

ISBN

978-3-95977-278-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ICALP.2023.75

Keywords in English

twin-width; planar graph

Abstract

V originále

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.

Links

MUNI/A/1081/2022, interní kód MU

Name: Modelování, analýza a verifikace (2023)

Investor: Masaryk University

MUNI/A/1433/2022, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Investor: Masaryk University

MUNI/I/1677/2018, interní kód MU

Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities

Citovat

HLINĚNÝ, Petr and Jan JEDELSKÝ. Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar. Online. In Etessami, Kousha and Feige, Uriel and Puppis, Gabriele. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2023, p. "75:1"-"75:18", 18 pp. ISBN 978-3-95977-278-5. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2023.75.

@inproceedings{2294838,
   author = {Hliněný, Petr and Jedelský, Jan},
   address = {Dagstuhl, Germany},
   booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2023.75},
   editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
   keywords = {twin-width; planar graph},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-278-5},
   pages = {"75:1"-"75:18"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar},
   year = {2023}
}

TY  - JOUR
ID  - 2294838
AU  - Hliněný, Petr - Jedelský, Jan
PY  - 2023
TI  - Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl, Germany
SN  - 9783959772785
KW  - twin-width
KW  - planar graph
N2  - 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.
ER  -

HLINĚNÝ, Petr and Jan JEDELSKÝ. Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar. Online. In Etessami, Kousha and Feige, Uriel and Puppis, Gabriele. \textit{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2023, p.~''75:1''-''75:18'', 18 pp. ISBN~978-3-95977-278-5. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2023.75.

Detailed Information on Publication Record