2026-07-21T15:07:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25824 2026-06-23T12:59:03Z ddc:004 open_access

Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs Bläsius, Thomas Dohse, Emil Haun, Deborah Merker, Laura hyperbolic uniform disk graphs product structure treewidth Hyperbolic uniform disk graphs (HUDGs) are intersection graphs of disks with some radius r in the hyperbolic plane, where r may be constant or depend on the number of vertices in a family of HUDGs. We show that HUDGs with constant clique number do not admit product structure, i.e., that there is no constant c such that every such graph is a subgraph of H ⊠ P for some graph H of treewidth at most c. This justifies that HUDGs are described as not having a grid-like structure in the literature, and is in contrast to unit disk graphs in the Euclidean plane, whose grid-like structure is evident from the fact that they are subgraphs of the strong product of two paths and a clique of constant size [Dvořák et al., '21, MATRIX Annals]. By allowing H to be any graph of constant treewidth instead of a path-like graph, we reject the possibility of a grid-like structure not merely by the maximum degree (which is unbounded for HUDGs) but due to their global structure. We complement this by showing that for every (sub-)constant r, HUDGs admit product structure, whereas the typical hyperbolic behavior is observed if r grows with the number of vertices. Our proof involves a family of n-vertex HUDGs with radius log n that has bounded clique number but unbounded treewidth, and one for which the ratio of treewidth and clique number is log n / log log n. Up to a log log n factor, this negatively answers a question raised by Bläsius et al. [SoCG '25] asking whether balanced separators of HUDGs with radius log n can be covered by less than log n cliques. Our results also imply that the local and layered tree-independence number of HUDGs are both unbounded, answering an open question of Dallard et al. [arXiv '25]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Bläsius and Emil Dohse and Deborah Haun and Laura Merker 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.18 urn:nbn:de:0030-drops-258249 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode