{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreic74l3fw5d54dsvdvw5yb3zunpzrxieyhvi5w5ntwsvgt6aas2q4m",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhhp3dok2722"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.18997v1",
  "publishedAt": "2026-03-20T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Thomas Bläsius",
    "Emil Dohse",
    "Deborah Haun",
    "Laura Merker"
  ],
  "textContent": "**Authors:** Thomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker\n\nHyperbolic 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"
}