A Coarse Geometric Approach to Graph Layout Problems
Journal of Graph Theory · 2026-10 · 113 (2) · 169-194
DOI: 10.1002/jgt.70058 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 05.05.2026. Verfasst von Wanying Huang und 3 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We define a range of new coarse geometric invariants based on various graph–theoretic measures of complexity for finite graphs, including treewidth, pathwidth, cutwidth and bandwidth. We prove that, for bounded degree graphs, these invariants can be used to define functions which satisfy a strong monotonicity property, namely, they are monotonically nondecreasing with respect to a large‐scale geometric generalisation of graph inclusion, and as such have potential applications in coarse geometry and geometric group theory. On the graph–theoretic side, we prove asymptotically optimal bounds on most of the above widths for the family of all finite subgraphs of any bounded degree graph whose separation profile is known to be of the form for some . This large class includes Diestel–Leader graphs, all Cayley graphs of nonvirtually cyclic polycyclic groups, uniform lattices in almost all connected unimodular Lie groups, and many hyperbolic groups.
Zitieren
APA
Huang, W., Hume, D., Kelly, S. J., & Lam, R. (2026). A Coarse Geometric Approach to Graph Layout Problems. Journal of Graph Theory, 113(2), 169-194. https://doi.org/10.1002/jgt.70058
Vancouver
Huang W, Hume D, Kelly SJ, Lam R. A Coarse Geometric Approach to Graph Layout Problems. Journal of Graph Theory. 2026;113(2):169-194. doi:10.1002/jgt.70058
BibTeX
@article{Huang2026,
author = {Huang, Wanying and Hume, David and Kelly, Samuel J. and Lam, Ryan},
title = {A Coarse Geometric Approach to Graph Layout Problems},
journal = {Journal of Graph Theory},
year = {2026},
volume = {113},
number = {2},
pages = {169--194},
doi = {10.1002/jgt.70058}
}
EUVIMED