Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910060145278976 |
|---|---|
| author | Bläsius, Thomas Dohse, Emil Haun, Deborah Merker, Laura |
| author_facet | Bläsius, Thomas Dohse, Emil Haun, Deborah Merker, Laura |
| contents | 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 \emph{product structure}, i.e., that there is no constant $c$ such that every such graph is a subgraph of $H \boxtimes 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18997 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs Bläsius, Thomas Dohse, Emil Haun, Deborah Merker, Laura Combinatorics Computational Geometry Discrete Mathematics 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 \emph{product structure}, i.e., that there is no constant $c$ such that every such graph is a subgraph of $H \boxtimes 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]. |
| title | Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs |
| topic | Combinatorics Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2603.18997 |