Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

In this paper, we investigate the structure of hyperbolic uniform disk graphs (HUDGs), i.e., graphs $G$ for which there is an $r$ such that $G$ is the intersection graph of disks with radius $r$ in the hyperbolic plane. The structure of these graphs heavily depends on $r$, where $r$ may be constant or a function depending on the number $n$ of vertices for a family of HUDGs. In the literature [3, 5], HUDGs with very small $r$ are described as almost Euclidean or grid-like, and as firmly hyperbolic or more hierarchical for larger $r$; see Figure 1. However, the state of the art cannot fully explain in what sense the grid-like structure depends on $r$. We contribute to the understanding of the structure of HUDGs by formalizing when a graph has a grid-like structure and showing that this is indeed not satisfied by HUDGs, unless the radius is small. We do so by showing that HUDGs do not admit a so-called product structure, and thereby also deepen the understanding of this notion. Before stating our results precisely, we review what is already known on the structure of HUDGs and how it depends on the radius $r$.

We start with small radii and work our way up from there. Locally, the hyperbolic plane behaves like the Euclidean plane, which sets the expectation that very small $r$ yield graphs similar to Euclidean unit disk graphs (EUDGs), which are defined as intersection graphs of unit disks in the Euclidean plane. While there are always HUDGs that are not EUDGs independent of how small we choose $r$, every EUDG is in fact a HUDG if we choose $r$ sufficiently small [3]. Sufficiently small here means that $r$ shrinks with the number of vertices $n$. EUDGs [8] are a well studied graph class that allows for balanced separators that can be covered with $O(\sqrt{n})$ cliques [14]. We remark that balanced separators are arguably one of the main reasons why HUDGs, EUDGs, and more generally disk graphs, are interesting from an algorithmic perspective. For HUDGs, there are balanced separators that can be covered with $O((1+1/r)\log n)$ cliques [5]. Interestingly, this matches the $\sqrt{n}$ bound of the Euclidean case for $r\in \mathrm{\Theta }(1/\sqrt{n})$ up to a $\log n$ factor and improves for larger $r$. In fact, if $r\in \mathrm{\Omega }(1)$, this gives separators coverable with $\log n$ cliques. This gives a strong argument that the structure of HUDGs changes when going from sub-constant to at least constant $r$. This change in structure is also reflected in the fact that several problems can be solved more efficiently for constant $r$ than in the Euclidean setting [30, 5]. Summarizing, there is strong evidence that the structure of HUDGs change significantly between sub-constant $r$ and constant $r$.

This raises the question whether there is a similar structural difference between constant $r$ and super-constant $r$. While the above separators do not continue to get smaller, there are indications that super-constant $r$ makes a difference, and that in particular $r\in \mathrm{\Theta }(\log n)$ is an interesting case. For HUDGs with $r\in \mathrm{\Theta }(\log n)$, the independent set problem can be solved in polynomial time [5]. Moreover, HUDGs with $r\in \mathrm{\Theta }(\log n)$ and random vertex positions are so-called hyperbolic random graphs [31]; a random graph model that is popular due to its resemblance to real-world networks in regards to properties like clustering, diameter, and degree distribution [23, 22, 26]. While this indicates a significant difference between constant and growing $r$, the state of the art does not make the structural differences explicit. The only structural insight we are aware of is that large stars, or more generally high-degree vertices with sparse neighborhoods, require $r$ to grow logarithmically with the degree [3].

The main result of this paper is to show that every class of HUDGs with constant radius $r$ has product structure, while there are HUDGs with growing radius that do not. This closes two gaps in the literature: First, it justifies why HUDGs with large radii should be considered not grid-like. And second, the contrast to HUDGs with constant radius shows a stark structural difference between constant radius compared to larger radii, say $\log n$.

Concerning the notion of grid-like structure, observe that $\sqrt{n}\times \sqrt{n}$-grids are EUDGs and thus also HUDGs for small radius. However, the grid-like structure of EUDGs goes far beyond merely containing grids. In fact, EUDGs are in general rather grid-like in the sense that there may be large cliques locally, but the global structure of every EUDG behaves like (the subgraph of) a grid. This notion of being “grid-like” can be formalized using the strong product of graphs, which we introduce formally in Section 2. For now, it suffices to know that the strong product $P_a⊠P_b$ of two paths on $a$ and $b$ vertices, respectively, is the $a\times b$-grid with diagonals. Moreover, the strong product $H⊠K_k$ of a graph $H$ with the complete graph $K_k$ expands each vertex of $H$ to a $k$-clique as shown in Figure 2. Dvořák, Huynh, Joret, Liu, and Wood [20] show that every EUDG $G$ is a subgraph of $P⊠P⊠K_k$, where $P$ is a path and $k$ is linear in the clique number $\omega$ of $G$. Equivalently, one can partition the vertices of a EUDG into sets of size $O(\omega )$ so that contracting each set into a single vertex yields a subgraph $H$ of a grid (with diagonals), yielding a product of the form $H⊠K_k$.

More generally, the concept of product structure allows us to view the graphs of a graph class as subgraphs of the product of simpler graphs; usually a graph with small treewidth and a path. We say a graph class $𝒢$ admits product structure if for every $G\in 𝒢$, we have $G\subseteq H^{\prime \prime }⊠P$ for some graph $H^{\prime \prime }$ of constant treewidth and some path $P$. In our proofs, we show a stronger statement, namely that the graphs we consider are subgraphs of $H⊠K_k$ for some hyperbolic tiling $H$. Since planar graphs, which include hyperbolic tilings, admit product structure, this implies $H\subseteq H^{\prime }⊠P⊠K_3$ for some graph $H$ of constant treewidth [16, 17], so with $H^{\prime \prime }=H^{\prime }⊠K_3⊠K_k$ we obtain a product of the form $H^{\prime \prime }⊠P$. Note that the above mentioned result on EUDGs can be viewed in this framework by choosing $H=P⊠P$. We remark that replacing one of the paths in the product $P⊠P⊠K_k$ by a graph $H^{\prime }$, enables graphs that go beyond Euclidean square-grids. In particular, it allows for high-degree vertices. That is, rejecting a grid-like structure via product structure is significantly stronger than showing that a graph class does not allow for a decomposition of the form $P⊠P⊠K_k$. To finish the discussion on grid-like structure, let us mention that “having product structure” does not need to be seen as a binary decision. For this, the row-treewidth of a graph $G$ is the smallest $t$ such that $G\subseteq H^{\prime \prime }⊠P$ for some graph $H^{\prime \prime }$ of treewidth $t$ and some path $P$. The row-treewidth of a graph class is the maximum row-treewidth among all contained graphs, possibly as a function depending on the number of vertices if it is unbounded. Now, among graph classes admitting product structure, we consider a class to have a stronger grid-like structure if the row-treewidth is small.

Our results that some families of HUDGs admit product structure while others do not, make HUDGs also interesting from the product structure perspective. Product structure has proved to be a useful tool for many graph-theoretic (see [28] for a survey) and algorithmic [1, 6] applications. While naturally, the literature concentrates on graph classes that admit product structure [16, 7, 28, 27, 15, 19], it is also interesting to find graph classes that do not admit product structure, for an other reason than the presence of large cliques. Interestingly, many known constructions are geometric intersection graphs, namely different kinds of string graphs with constant clique number [32, 29]. By showing that HUDGs do not admit product structure, we contribute to an improved understanding of the limitations of this notion.

We assume familiarity with some graph-theoretic terminology; also see the full version [2].

In this section, we show that HUDGs with constant clique number do not admit product structure (Theorem 1). While our construction initially has disk radius $\mathrm{\Theta }(\log n)$, we extend it to arbitrary super-constant disk radii to prove the second part of Theorem 2. This is tight as we show in Section 4 that every family of HUDGs with disk radius in $O(1)$ and constant clique number has indeed product structure. Similarly, we provide families of HUDGs for the lower bounds in the second row of Table 1 for every super-constant disk radius. These results are summarized in Corollaries 15 and 16 at the end of the section.

To reject product structure, we use that, asymptotically, the treewidth in the neighborhood of some vertex is a lower bound on the row-treewidth [18, 16]. Since SHUDGs describe the neighborhoods of vertices in a HUDG, we aim for a family of SHUDGs with constant clique number but unbounded treewidth to prove Theorem 1 (see the full version [2] for details).

We then identify an induced subgraph within each of the constructed SHUDGs to prove Theorem 1. In addition, Theorems 6 and 7 together prove Theorem 4.

In this section, we show that HUDGs whose disk radius and clique number are (sub-)constant admit product structure, which finishes the proof of Theorem 2. In fact, we show that every HUDG $G$ with disk radius $r$ and clique number $\omega$ is a subgraph of $H⊠K_k$, where $H$ is a hyperbolic tiling and $k\in O(\omega \cdot 3^{8r})$, which emphasizes their grid-structure. Since $H$ is planar, and planar graphs are subgraphs of $H^{\prime }⊠P⊠K_3$ with $\mathrm{tw}(H^{\prime })=3$ [16], it follows that $G\subseteq H^{\prime }⊠P⊠K_{3k}$. This implies that $G\subseteq H^{\prime \prime }⊠P$ for the graph $H^{\prime \prime }=H^{\prime }⊠K_{3k}$ of treewidth $O(\omega \cdot 3^{8r})$, i.e., $G$ has row-treewidth $O(\omega \cdot 3^{8r})$. Thus, in the following theorem, the product $H⊠K_{O(\omega \cdot 3^{8r})}$ is the strongest statement and the others follow.

Note that Theorem 17 indeed implies the first part of Theorem 2 since the row-treewidth only depends on $\omega$ and $r$, and thus we obtain product structure for every graph class with (sub-)constant clique number and disk radius. Further note that we also obtain an upper bound on the row-treewidth if clique number or disk radius are super-constant for some family of HUDGs. However, in these cases the upper bound on the row-treewidth also grows and thus we do not obtain product structure, which is no surprise given Section 3.

Recall that [20] shows that EUDGs with clique number $\omega$ are subgraphs of $H⊠K_{O(\omega )}$, where $H$ is a square-grid with diagonals. To find the product $H⊠K_k$ for HUDGs, we lift their approach to the hyperbolic setting with two major changes. Not surprisingly, we replace the Euclidean tiling by a hyperbolic tiling to adjust to the geometry. However, we also need to face different disk radii since, in contrast to [20], we cannot freely choose the size of our tiles. For large disk radii, we solve this by merging tiles, whereas we subdivide tiles for small disk radii as needed. To do so, we provide a geometric interpretation of what we aim for. Two tiles are called adjacent if they are adjacent in the dual, i.e., if they share an edge.

Observe that this indeed implies that every HUDG with radius $r$ and clique number $\omega$ is a subgraph of $H⊠K_k$, where $H$ is the dual of the tiling from Theorem 3, and $k\in O(\omega \cdot 3^{8r})$. To see this, consider the partition $𝒫$ with one part for the vertices of each tile. By the first property, each part contains at most $O(\omega \cdot 3^{8r})$ vertices since each disk of radius $r$ covers a clique and thus at most $\omega$ vertices. Thus, we have $G\subseteq Q⊠K_k$ for the quotient $Q=G/𝒫$ that is obtained by contracting the vertices in each tile, and some $k\in O(\omega \cdot 3^{8r})$. Then, by the second property, the endpoints of every edge lie in the same or in adjacent tiles, so the quotient $Q$ is a subgraph of the dual $H$ of the tiling from Theorem 3. Together, we obtain $G\subseteq Q⊠K_k\subseteq H⊠K_k$, as required by Theorem 17.

The main challenge of this section is to prove Theorem 3, for which we refer to the full version [2]. For an overview, if $r$ is at least some carefully chosen constant, we start with a regular $\{7,3\}$-tiling whose tiles are merged until the second property of Theorem 3 is satisfied (Figure 8). Here, the tiles have a rapidly growing maximum degree to meet the requirements of the hyperbolic plane. The case for small radii then starts with a regular $\{4,5\}$-tiling, where we subdivide the tiles until they are small enough for the first property (see Figure 9). This results in a tiling that gets more Euclidean the smaller $r$ is, in the sense that locally, it looks like a Euclidean square grid.

In this paper, we characterize for which functions $r$ families of HUDGs with constant clique number and disk radius $r$ admit product structure: If $r\in O(1)$, then every family has bounded row-treewidth and thus admits product structure, otherwise there are families with unbounded row-treewidth. However, our upper bound is exponential in the disk radius, whereas our lower bound is logarithmic. It is an interesting open question whether the exponential dependency is necessary, both for Theorems 3 and 17. We conjecture that it is indeed necessary for the tiling, but believe that the base can be improved, which would also improve the bound on the row-treewidth. Note that even if there is an exponential lower bound for the tiling, it does not necessarily transfer to the row-treewidth of HUDGs.

With our lower-bound construction, we show that there are SHUDGs with radius $\mathrm{\Theta }(\log n)$ having treewidth $\mathrm{\Omega }(\omega \frac{\log n}{\log \log n})$. This almost matches the upper bound of $O(\omega \cdot \log n)$ [5, 21]. We ask whether the remaining gap can be closed. Moreover, we ask whether similar lower bounds are possible for other clique numbers than $\omega \in O(\log \log n)$; specifically for constant $\omega$.

Finally, we conjecture that our lower bound for the row-treewidth stops growing at logarithmic grid radius because there are no HUDGs that require larger radius.