On a tree-based variant of bandwidth and forbidding simple topological minors
Hugo Jacob, William Lochet, Christophe Paul · 2025
Read On a tree-based variant of bandwidth and forbidding simple topological minors by Hugo Jacob, William Lochet, Christophe Paul (2025) 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-2502-11674.txt.
Introduction
Hugo Jacob, William Lochet, and Christophe Paul study a tree-shaped way to lay out graphs, in a 2025 math study. A graph links points by edges. Bandwidth lays those points on a line so linked points sit close. Their variant, treebandwidth, lays points on a rooted tree so linked points sit in a parent-child line.
The trio prove shape rules for graphs that bar two small forms: a fan and a dipole, each barred as a bent copy inside the graph. Those rules can be computed fast for fixed bounds. From them, the team builds a fast near-best solver for treebandwidth. They also pin down how hard the exact task is, which tells other scholars where fast exact tools can and cannot exist.
Catalog record
| CREATOR | Hugo Jacob, William Lochet, Christophe Paul |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 141 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-11674