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 a Jan JEDELSKÝ

Základní údaje

Originální název

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

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Jan JEDELSKÝ (203 Česká republika, domácí)

Vydání

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

Nakladatel

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

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

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:00131119

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-278-5

ISSN

DOI

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

Klíčová slova anglicky

twin-width; planar graph

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 4. 2024 23:06, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

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

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

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)

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

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

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

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

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

HLINĚNÝ, Petr a 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, s. "75:1"-"75:18", 18 s. ISBN 978-3-95977-278-5. Dostupné z: 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 a 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, s.~''75:1''-''75:18'', 18 s. ISBN~978-3-95977-278-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ICALP.2023.75.

Podrobný výpis o publikaci