A structural duality for path-decompositions into parts of small radius
Albrechtsen, Sandra1; Diestel, Reinhard1; Elm, Ann-Kathrin2; Fluck, Eva3; Jacobs, Raphael W.1; Knappe, Paul1; Wollan, Paul4
1University of Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Hamburg (Germany)
2Universität Heidelberg, Department of Computer Science, Im Neuenheimer Feld 205, 69120 Heidelberg (Germany)
3RWTH Aachen University, Department of Computer Science, Ahornstraße 55, 52074 Aachen (Germany)
4University of Rome, “La Sapienza”, Department of Computer Science, Via Salaria 113, 00198 Rome (Italy)
Innovations in Graph Theory, Volume 3 (2026), pp. 207-246

It is an easy observation that if a graph $G$ admits a path-decomposition whose parts have small radius, then $G$ contains no large subdivision of $K_{1,3}$ or $K^3$ as a (quasi-)geodesic subgraph. We show that these are in fact the only obstructions to such path-decompositions of small radial width, and we prove analogous results for decompositions modelled on cycles and subdivided stars instead of paths.

With our results we confirm in a strong form a conjecture of Georgakopoulos and Papasoglu on fat-minor-characterisations of graphs quasi-isometric to paths, cycles and paths, and subdivided stars, respectively. For this, we present a novel view on quasi-isometries between graphs by graph-decompositions of bounded radial width and spread. This new perspective enables us to prove further results in coarse graph theory, and may thus be of independent interest.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.22
Classification: 05C10, 05C75, 05C12, 05C62, 05C83
Keywords: Path-Decompositions, Graph-Decompositions, Radial Width, Quasi-Isometry, Geodesic, Topological Minors, Fat minors

Albrechtsen, Sandra  1 ; Diestel, Reinhard  1 ; Elm, Ann-Kathrin  2 ; Fluck, Eva  3 ; Jacobs, Raphael W.  1 ; Knappe, Paul  1 ; Wollan, Paul  4

1 University of Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Hamburg (Germany)
2 Universität Heidelberg, Department of Computer Science, Im Neuenheimer Feld 205, 69120 Heidelberg (Germany)
3 RWTH Aachen University, Department of Computer Science, Ahornstraße 55, 52074 Aachen (Germany)
4 University of Rome, “La Sapienza”, Department of Computer Science, Via Salaria 113, 00198 Rome (Italy)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Albrechtsen, Sandra; Diestel, Reinhard; Elm, Ann-Kathrin; Fluck, Eva; Jacobs, Raphael W.; Knappe, Paul; Wollan, Paul. A structural duality for path-decompositions into parts of small radius. Innovations in Graph Theory, Volume 3 (2026), pp. 207-246. doi: 10.5802/igt.22
@article{IGT_2026__3__207_0,
     author = {Albrechtsen, Sandra and Diestel, Reinhard and Elm, Ann-Kathrin and Fluck, Eva and Jacobs, Raphael W. and Knappe, Paul and Wollan, Paul},
     title = {A structural duality for path-decompositions into parts of small radius},
     journal = {Innovations in Graph Theory},
     pages = {207--246},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.22},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.22/}
}
TY  - JOUR
AU  - Albrechtsen, Sandra
AU  - Diestel, Reinhard
AU  - Elm, Ann-Kathrin
AU  - Fluck, Eva
AU  - Jacobs, Raphael W.
AU  - Knappe, Paul
AU  - Wollan, Paul
TI  - A structural duality for path-decompositions into parts of small radius
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 207
EP  - 246
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.22/
DO  - 10.5802/igt.22
LA  - en
ID  - IGT_2026__3__207_0
ER  - 
%0 Journal Article
%A Albrechtsen, Sandra
%A Diestel, Reinhard
%A Elm, Ann-Kathrin
%A Fluck, Eva
%A Jacobs, Raphael W.
%A Knappe, Paul
%A Wollan, Paul
%T A structural duality for path-decompositions into parts of small radius
%J Innovations in Graph Theory
%D 2026
%P 207-246
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.22/
%R 10.5802/igt.22
%G en
%F IGT_2026__3__207_0

[1] Abrishami, Tara; Knappe, Paul; Kobler, Jonas Locally chordal graphs (2025) | arXiv | Zbl

[2] Albrechtsen, Sandra; Diestel, Reinhard; Elm, Ann-Kathrin; Fluck, Eva; Jacobs, Raphael W.; Knappe, Paul; Wollan, Paul A structural duality for path-decompositions into parts of small radius (2023) | arXiv

[3] Albrechtsen, Sandra; Distel, Marc; Georgakopoulos, Agelos Excluding K 2,t as a fat minor (2025) | arXiv

[4] Albrechtsen, Sandra; Distel, Marc; Georgakopoulos, Agelos Small counterexamples to the fat minor conjecture (2026) | arXiv | Zbl

[5] Albrechtsen, Sandra; Jacobs, Raphael W.; Knappe, Paul; Wollan, Paul A characterisation of graphs quasi-isometric to K 4 -minor-free graphs, Combinatorica, Volume 45 (2025) no. 6, Paper no. 61, 36 pages | Zbl | MR

[6] Belmonte, Rémy; Fomin, Fedor V.; Golovach, Petr A.; Ramanujan, M. S. Metric dimension of bounded tree-length graphs, SIAM J. Discrete Math., Volume 31 (2017) no. 2, pp. 1217-1243 | DOI | Zbl | MR

[7] Bendele, Oliver; Rautenbach, Dieter Additive tree O(ρlogn)-spanners from tree breadth ρ, Theor. Comput. Sci., Volume 914 (2022), pp. 39-46 | Zbl | DOI | MR

[8] Berger, Eli; Seymour, Paul D. Bounded-diameter tree-decompositions, Combinatorica, Volume 44 (2024), pp. 659-674 | MR | Zbl | DOI

[9] Chepoi, Victor; Dragan, Feodor F.; Newman, Ilan; Rabinovich, Yuri; Vaxès, Yann Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs, Discrete Comput. Geom., Volume 47 (2012), pp. 187-214 | MR | DOI | Zbl

[10] Davies, James; Hickingbotham, Robert; Illingworth, Freddie; McCarty, Rose Fat minors cannot be thinned (by quasi-isometries) (2024) | arXiv | Zbl

[11] Diestel, Reinhard Graph Theory, Graduate Texts in Mathematics, 173, Springer, 2025 | DOI

[12] Diestel, Reinhard; Jacobs, Raphael W.; Knappe, Paul; Kurkofka, Jan Canonical graph decompositions via coverings, extended version (2022) | arXiv | Zbl

[13] Diestel, Reinhard; Jacobs, Raphael W.; Knappe, Paul; Kurkofka, Jan Canonical graph decompositions via coverings (2026) (to appear in Trans. Am. Math. Soc.) | arXiv

[14] Diestel, Reinhard; Kühn, Daniela Graph minor hierarchies, Discrete Appl. Math., Volume 145 (2005), pp. 167-182 | DOI | MR | Zbl

[15] Dourisboure, Yon; Gavoille, Cyril Tree-decompositions with bags of small diameter, Discrete Math., Volume 307 (2007) no. 16, pp. 2008-2029 | DOI | Zbl | MR

[16] Dragan, Feodor F.; Köhler, Ekkehard An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs, Algorithmica, Volume 69 (2014), pp. 884-905 | DOI | Zbl | MR

[17] Fujiwara, Koji; Papasoglu, Panos A coarse-geometry characterization of cacti (2023) | arXiv | Zbl

[18] Georgakopoulos, Agelos; Papasoglu, Panos Graph minors and metric spaces, Combinatorica, Volume 45 (2025) no. 33, Paper no. 33, 29 pages | MR | Zbl

[19] Gromov, Mikhael Geometric group theory. Volume 2: Asymptotic invariants of infinite groups. Proceedings of the symposium held at the Sussex University, Brighton, July 14-19, 1991, London Mathematical Society Lecture Note Series, 182, Cambridge University Press, 1993 | MR | Zbl

[20] Jacobs, Raphael W.; Knappe, Paul; Kurkofka, Jan Canonical graph decompositions via local separations (2025) | arXiv

[21] Leitert, Arne Tree-Breadth of Graphs with Variants and Applications, Ph. D. Thesis, Kent State University (2017)

[22] Löh, Clara Geometric Group Theory. An Introduction, Universitext, Springer, 2017 | MR | Zbl

[23] Nguyen, Tung; Scott, Alex; Seymour, Paul D. Asymptotic Structure. II. Path-width and Additive Quasi-Isometry (2025) | arXiv

[24] Robertson, Neil; Seymour, Paul D. Graph Minors. II. Algorithmic Aspects of Tree-Width, J. Algorithms, Volume 7 (1986), pp. 309-322 | DOI | MR | Zbl

[25] Robertson, Neil; Seymour, Paul D. Graph Minors. V. Excluding a Planar Graph, J. Comb. Theory, Ser. B, Volume 41 (1986), pp. 92-114 | DOI | MR | Zbl

Cited by Sources: