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

CREATORHugo Jacob, William Lochet, Christophe Paul
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE141 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-11674

Browse the full library · About the Tower of Babel