Twin-width of graphs on surfaces

D 2024

Twin-width of graphs on surfaces

KRÁĽ, Daniel; Kristýna PEKÁRKOVÁ a Kenny ŠTORGEL

Základní údaje

Originální název

Twin-width of graphs on surfaces

Autoři

KRÁĽ, Daniel; Kristýna PEKÁRKOVÁ a Kenny ŠTORGEL

Vydání

Dagstuhl, Germany, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), od s. "66:1"-"66:15", 15 s. 2024

Nakladatel

Schloss Dagstuhl – Leibniz-Zentrum fü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/24:00137364

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-335-5

ISSN

EID Scopus

2-s2.0-85203345075

Klíčová slova anglicky

twin-width; graphs on surfaces; fixed parameter tractability

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 30. 7. 2025 14:57, Mgr. Michal Petr

Anotace

V originále

Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. Hliněný and Jedelský [ICALP'23] showed that every planar graph has twin-width at most 8. We prove that the twin-width of every graph embeddable in a surface of Euler genus g is at most 18√{47g} + O(1), which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus g that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size max{6, 32g-37}.

Návaznosti

MUNI/A/1592/2023, interní kód MU

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

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

MUNI/A/1608/2023, interní kód MU

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

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

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

KRÁĽ, Daniel; Kristýna PEKÁRKOVÁ a Kenny ŠTORGEL. Twin-width of graphs on surfaces. Online. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, s. "66:1"-"66:15", 15 s. ISBN 978-3-95977-335-5.

@inproceedings{2444615,
   author = {Kráľ, Daniel and Pekárková, Kristýna and Štorgel, Kenny},
   address = {Dagstuhl, Germany},
   booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
   keywords = {twin-width; graphs on surfaces; fixed parameter tractability},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-335-5},
   pages = {"66:1"-"66:15"},
   publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
   title = {Twin-width of graphs on surfaces},
   year = {2024}
}

TY  - CONF
ID  - 2444615
AU  - Kráľ, Daniel - Pekárková, Kristýna - Štorgel, Kenny
PY  - 2024
TI  - Twin-width of graphs on surfaces
PB  - Schloss Dagstuhl – Leibniz-Zentrum für Informatik
CY  - Dagstuhl, Germany
SN  - 9783959773355
KW  - twin-width
KW  - graphs on surfaces
KW  - fixed parameter tractability
N2  - Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. Hliněný and Jedelský [ICALP'23] showed that every planar graph has twin-width at most 8. We prove that the twin-width of every graph embeddable in a surface of Euler genus g is at most 18√{47g} + O(1), which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus g that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size max{6, 32g-37}.
ER  -

KRÁĽ, Daniel; Kristýna PEKÁRKOVÁ a Kenny ŠTORGEL. Twin-width of graphs on surfaces. Online. In \textit{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, s.~''66:1''-''66:15'', 15 s. ISBN~978-3-95977-335-5.

Přehled o publikaci