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

CREATORThomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121055
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18997

Browse the full library · About the Tower of Babel