Quickly excluding an annotated planar graph
Maximilian Gorsky Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Evangelos Protopapas Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland Sebastian Wiederrecht School of Computing, KAIST, Daejeon, South Korea · 2026
Read Quickly excluding an annotated planar graph by Maximilian Gorsky Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Evangelos Protopapas Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland Sebastian Wiederrecht School of Computing, KAIST, Daejeon, South Korea (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-06516.txt.
Description
Graph parameters that generalize treewidth help explain why many hard problems become tractable on planar graphs. Maximilian Gorsky and 2 co-authors prove polynomial bounds for a key structure result about vertex sets of bounded bidimensionality. Bidimensionality blends treewidth with the face-cover number of a vertex set.
The structure theorem decomposes a graph into pieces where the behavior of a marked terminal set stays tightly controlled, much like the Grid Theorem of Robertson and Seymour in rooted form. Combining recent polynomial bounds from graph minors theory with new tools for annotated vertex sets, the authors bound every parameter in the theorem. An application sketch shows the same techniques yield polynomial bounds for a related problem family.
Catalog record
| CREATOR | Maximilian Gorsky Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Evangelos Protopapas Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland Sebastian Wiederrecht School of Computing, KAIST, Daejeon, South Korea |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 257 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-06516