On a tree-based variant of bandwidth and forbidding simple topological minors
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917925459329024 |
|---|---|
| author | Jacob, Hugo Lochet, William Paul, Christophe |
| author_facet | Jacob, Hugo Lochet, William Paul, Christophe |
| contents | We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole ($K_{2,k}$) as a topological minor. The corresponding decompositions can be computed in FPT linear time. This is motivated by the study of a graph parameter we call treebandwidth which extends the graph parameter bandwidth by replacing the linear layout by a rooted tree such that neighbours in the graph are in ancestor-descendant relation in the tree.
We deduce an approximation algorithm for treebandwidth running in FPT linear time from our structure theorems. We complement this result with a precise characterisation of the parameterised complexity of computing the parameter exactly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11674 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On a tree-based variant of bandwidth and forbidding simple topological minors Jacob, Hugo Lochet, William Paul, Christophe Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole ($K_{2,k}$) as a topological minor. The corresponding decompositions can be computed in FPT linear time. This is motivated by the study of a graph parameter we call treebandwidth which extends the graph parameter bandwidth by replacing the linear layout by a rooted tree such that neighbours in the graph are in ancestor-descendant relation in the tree. We deduce an approximation algorithm for treebandwidth running in FPT linear time from our structure theorems. We complement this result with a precise characterisation of the parameterised complexity of computing the parameter exactly. |
| title | On a tree-based variant of bandwidth and forbidding simple topological minors |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2502.11674 |