Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs
Thomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker · 2026
Read Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs by Thomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker (2026) 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-2603-18997.txt.
Description
Blasius and co-authors ask whether disk graphs in hyperbolic space have a grid-like product form. Such graphs join disks of one radius that overlap in the curved plane. They show that with a fixed clique cap, no such product form exists. This sets them apart from flat-plane disk graphs, which do have that form. For very small radii, the product form does hold. The split turns on whether the radius grows with graph size. Their proof uses a family with slow radius growth and no grid structure.
Catalog record
| CREATOR | Thomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121055 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18997