Twin-width of graphs on surfaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911773999759360 |
|---|---|
| author | Kráľ, Daniel Pekárková, Kristýna Štorgel, Kenny |
| author_facet | Kráľ, Daniel Pekárková, Kristýna Štorgel, Kenny |
| contents | Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin-width of every graph embeddable in a surface of Euler genus $g$ is $18\sqrt{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\{8,32g-27\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_05811 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Twin-width of graphs on surfaces Kráľ, Daniel Pekárková, Kristýna Štorgel, Kenny Combinatorics Discrete Mathematics Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin-width of every graph embeddable in a surface of Euler genus $g$ is $18\sqrt{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\{8,32g-27\}$. |
| title | Twin-width of graphs on surfaces |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2307.05811 |