Structure and Independence in Hyperbolic Uniform Disk Graphs

Given a set of disks in the plane, one can assign to them a geometric intersection graph whose vertices are the disks, and edges are added between pairs of intersecting disks. The study of intersection graphs is usually motivated by physically realized networks: such networks require spatial proximity between vertices for successful connections, and the simplest model allows for connections within a distance $2$, which is equivalent to the intersection graph induced by disks of radius $1$ centered at the vertices. Such graphs are called unit disk graphs.

Unit disk graphs have received a lot of attention in the theoretical computer science literature. Their intriguing structural properties yield profound mathematical insights and facilitate the development of efficient algorithms. Historically, unit disk graphs have been studied in the Euclidean plane, where they are well motivated due to their relevance for, e.g., sensor networks. The relevance of unit disk graphs in the hyperbolic plane is less obvious. However, originating in the network science community, it has been observed [26] that the intersection graph of randomly sampled disks of equal radius $r$ yields graphs that resemble complex real-world networks in regards to important properties¹¹1For this to work, the choice of the radius $r$ is crucial. It is chosen as $r=\log n+c$ for a constant $c$ that controls the average degree, and the disk centers are all sampled within a disk of radius $2r$.. They are, e.g., heterogeneous with a degree distribution following a power law [19], have high clustering coefficient [19], and exhibit the small-world property [18, 35].

Besides numerous structural results, these hyperbolic random graphs also allow for the design of more efficient algorithms [7, 8, 4, 5]. However, all these results rely on the fact that the disks are chosen randomly. So far, there is only little research on hyperbolic uniform disk graphs from a deterministic, more graph-theoretic perspective. It is important to note that for the intersection graphs of radius-$r$ disks the resulting graph classes are different for different values of $r$. Moreover, it is natural to allow for the radius $r$ to be a (monotone) function of the number of vertices. Unlike the Euclidean setting where a simple scaling shows that the choice of “unit” does not matter, it is a crucial parameter in the hyperbolic setting.

For those unfamiliar with hyperbolic geometry there is a way to conceptually understand these graphs in a Euclidean setting as follows. One can think of a hyperbolic disk graph of radius $r$ disks as a Euclidean disk graph where the radius of a disk of center $p$ is set to $f_r(\mathrm{dist}(o,p))$, where $f_r$ is decreasing very quickly at a rate set by $r$, and $\mathrm{dist}(o,p)$ is the distance between the origin and the disk center $p$. In particular, as $r$ goes to $0$, the rate of decrease is negligible, and we get almost Euclidean unit disk graphs, while large $r$ corresponds to a very different graph class. See Figure 1 for an illustration.

This observation is formalized by stating that hyperbolic disk graphs of uniform (that is, equal) radius $1/n^3$ and uniform radius $\log n$ are incomparable: The former class contains the $k\times k$ grid graph with $n=k^2$ for all $k$, but does not contain stars of size $n\ge 8$. The latter contains all star graphs but does not contain any $k\times k$ grid of size $k\ge 5$. See Figure 1 for an illustration and the full version of this paper for a formal proof of these claims. We call the regime $r\le 1/\sqrt{n}$ almost Euclidean, while $r\in \mathrm{\Omega }(\log n)$ is called firmly hyperbolic.

The primary goal of our paper is to explore the following:

We note that one of the main challenges for large radii is that unlike the Euclidean plane, the kissing number²²2The kissing number of radius $r$ disks is the maximum number of interior-disjoint disks of radius $r$ that can touch a fixed disk of radius $r$. of hyperbolic disks of large radius is unbounded, and as a result, there may be arbitrarily many “nearby disks” to any given disks in the independent set. At the same time the larger the hyperbolic disks are, the harder it is to “surround” them with equal radius disks, which intuitively leads to a simpler structure.

The case of constant radius hyperbolic disks (with constant kissing number) has been studied by Kisfaludi-Bak [23], but these methods fail for super-constant kissing number. The case of radius roughly $\log n$ has only been studied in a more specialized setting (inspired by hyperbolic random graph models) in [6]. They call the relevant graph class strongly hyperbolic uniform disk graphs. The above-mentioned hyperbolic random graphs are randomly sampled strongly hyperbolic uniform disk graphs. Apart from these particular choices of the radius, we have very limited understanding about the structure of hyperbolic uniform disk graphs, and the results of [6] do not imply anything for our hyperbolic uniform disk graphs.

The radius’ impact on problem complexity was studied in the context of the traveling salesman problem, where one can use the minimum distance between points as a parameter with a similar flavor. In the hyperbolic plane, Kisfaludi-Bak [24] showed that the complexity of TSP decreases as one increases the minimum pairwise distance $r$ among input points. In this paper, we show that the structure of hyperbolic uniform disk graphs behaves similarly: their structure becomes easier for larger values of $r$, and Independent Set can be solved faster for larger $r$.

Let $\mathrm{HUDG}(r(n))$ denote the set of intersection graphs where each $n$-vertex graph can be realized as the intersection graph of disks of uniform (equal) radius $r(n)$ in the hyperbolic plane of Gaussian curvature³³3Equivalently, one can fix the radius to be $1$ and set the Gaussian curvature to be $-r^2$. $-1$. We denote by $\mathrm{HUDG}$ the union of these classes for all radii, that is, $\mathrm{HUDG}={\bigcup }_{\rho >0}\mathrm{HUDG}(\rho )$. Let $\mathrm{UDG}$ denote the class of unit disk graphs in the Euclidean plane. The authors in [6] have shown that $\mathrm{UDG}\subset \mathrm{HUDG}$. When a graph is given without the geometric realization, it is NP-hard (even $\exists ℝ$-complete) to decide if the graph is a $\mathrm{UDG}$ [33] or $\mathrm{HUDG}$ [3]; for this reason, we will assume throughout this article that the input intersection graphs of our algorithms are given by specifying their geometric realization. In the hyperbolic setting, one can specify the disk centers using a so-called model of the hyperbolic plane, which is simply an embedding of the hyperbolic plane into some specific part of the Euclidean plane, e.g., inside the Euclidean unit disk. See our preliminaries for a brief introduction to Euclidean models of the hyperbolic plane.

From the perspective of graph algorithms, unit disk graphs in the Euclidean plane have been serving an important role as a graph class that is not comparable, but similar to planar graphs. The circle packing theorem [25] states that every planar graph can be realized as an intersection graph of disks (of arbitrary radii); thus, disk graphs serve as a common generalization of planar and unit disk graphs. Using conformal hyperbolic models, one can observe that hyperbolic disks appear as Euclidean disks⁴⁴4In the Poincaré disk and half-plane models, all hyperbolic disks are Euclidean disks, but the Euclidean and hyperbolic radii of these disks are different. in the model, which means that all $\mathrm{HUDG}$s are realized as Euclidean disk graphs. Denoting Euclidean disk graphs with $\mathrm{DG}$, we thus have $\mathrm{UDG}\subseteq \mathrm{HUDG}\subseteq \mathrm{DG}$⁵⁵5With a little effort, one can show that both containments are strict: $\mathrm{UDG}⊊\mathrm{HUDG}⊊\mathrm{DG}$..

A key structural tool in the study of both planar and (unit) disk graphs has been separator theorems. By a result of Lipton and Tarjan[27], any $n$-vertex planar graph can be partitioned into three vertex sets, $A,B$, and the separator $S$, such that no edges go between $A$ and $B$, the separator set $S$ has size $𝒪(\sqrt{n})$, and $\max \{|A|,|B|\}\le \frac{2}{3}n$. Separator theorems are closely related to the treewidth⁶⁶6See the full version of this paper for definitions of treewidth and $𝒫$-flattened treewidth. of graphs [10], for example, the above separator implies a treewidth bound of $𝒪(\sqrt{n})$ on planar graphs.

For (unit) disk graphs, similar separators and treewidth bounds are not possible, because one can represent cliques of arbitrary size. There have been at least three different approaches to deal with large cliques. The first option is to bound the cliques in some way. One can, for example, obtain separators for a set of disks of bounded ply, i.e., assuming that each point of the ambient space is included in at most $\mathrm{\ell }$ disks. There are several separators for disks (and even balls in higher dimensions) that involve ply. The strongest and most general among these is by Miller, Teng, Thurston, and Vavasis [34]. The second way to deal with large cliques is to use so-called clique-based separators [15, 16], where the separator is decomposed into cliques and the cliques are sometimes assigned some small weight depending on their size. In the hyperbolic setting, Kisfaludi-Bak [23] showed that for any constant $c$, the graph class $\mathrm{HUDG}(c)$ admits a balanced separator consisting of $𝒪(\log n)$ cliques. The same paper shows that $\mathrm{HUDG}(c)$ also has clique-based separators of weight $𝒪({\log }^{2}n)$ and extends these techniques to balls of constant radius in higher-dimensional hyperbolic spaces, along with much of the machinery of [15]. The third option is to use random disk positions to disperse large cliques with high probability. Bläsius, Friedrich, and Krohmer [7] gave high-probability bounds on separators and treewidth for certain radius regimes in hyperbolic random graphs.

The above separators and treewidth can be used to obtain fast divide-and-conquer or dynamic programming algorithms [28, 15]. In the Independent Set problem, the goal is to decide if there are $k$ pairwise non-adjacent vertices in the graph. In general graphs, the best known algorithms run in $2^{𝒪(n)}$ or $n^{𝒪(k)}$ time, and these running times are optimal under the Exponential Time Hypothesis (ETH) [14] (see [22] for the definition of ETH). In planar and disk graphs however, the separators allow algorithms with running time $2^{𝒪(\sqrt{n})}$ or $n^{𝒪(\sqrt{k})}$ [14, 32]. Moreover, the separator implies that planar graphs have treewidth⁶ $𝒪(\sqrt{n})$ and unit disk graphs have so-called $𝒫$-flattened treewidth $𝒪(\sqrt{n})$ for some clique-partition $𝒫$. As a consequence, one can adapt treewidth-based algorithms [14] to these graph classes. In the hyperbolic setting, the ($𝒫$-flattened) treewidth bounds yield an $n^{𝒪(\log n)}$ quasi-polynomial algorithm for Independent Set and many other problems on graphs in $\mathrm{HUDG}(c)$ for any constant $c$, which is matched by a lower bound under ETH [23] in case of Independent Set.

When approximating Independent Set, the main algorithmic tool in planar graphs is Baker’s shifting technique [2] that gives a $(1-\epsilon )$-approximate independent set in $2^{𝒪(1/\epsilon )}n$ time. A conceptually easier grid shifting was discovered for unit disks by Hochbaum and Maas [21], which was later (implicitly) improved by Agarwal, van Kreveld, and Suri [1]. This line of research culminated in the algorithm of Chan [13] with a running time of $n^{𝒪(1/\epsilon )}$ for disks, which also can be generalized for balls in higher dimensions. Baker’s algorithm and Chan’s algorithm (even for unit disks) are optimal under standard complexity assumptions [30]. To the best of our knowledge, there are no published approximation algorithms for $\mathrm{HUDG}(r(n))$ or $\mathrm{HUDG}$ other than what is already implied from the algorithms on disk graphs. However, for hyperbolic random graphs, there is an $𝒪(m\log n)$ algorithm that yields a $1-o(1)$-approximation for Independent Set asymptotically almost surely [5].

An interesting setting, where the treewidth of planar graphs has been used for intersection graphs, is that of covering and packing problems in the work of Har-Peled and later Marx and Pilipczuk [20, 32]. For the Independent Set problem on unit disk graphs, they consider the Voronoi diagram of the disk centers of a maximum independent set of size $k$. For a set of points (often called sites) $S$, the Voronoi diagram is a planar subdivision (a planar graph) that partitions the plane according to the closest site of $S$, that is, the cell of a site $s\in S$ consists of those points whose nearest neighbor from $S$ is $s$. As the Voronoi diagram is a planar graph on $𝒪(k)$ vertices, it has a balanced separator of size $𝒪(\sqrt{k})$. Although this Voronoi diagram is based on the solution, and thus unknown from the algorithmic perspective, the idea of Marx and Pilipczuk is that one can enumerate all possible separators of the Voronoi diagram in $n^{𝒪(\sqrt{k})}$ time, and one of these separators can then be used to separate the (still unknown) solution in a balanced manner. A similar “separator guessing” technique has been used elsewhere in approximation and parameterized algorithms [31, 12].

We introduce fundamental definitions and notation used throughout the paper. Additional concepts and notation are introduced in their relevant sections as needed.

There are several intriguing future directions to explore in this space. First, is there a fully polynomial approximation scheme for Independent Set for $r\ge 1$? If not, is there at least an approximation scheme that is polynomial in $n$, quasi-polynomial in $1/\epsilon$, but independent of the ply?

Second, it would be interesting to explore separators in higher-dimensional hyperbolic spaces. The only case studied there is $r=\mathrm{\Theta }(1)$ [23]. One may expect that separator size should also decrease with growing $r$. Is there a constant $c_d$ such that Independent Set can be solved in polynomial time in ${ℍ}^d$ when $r\ge c_d\log n$?

Third, we should explore uniform disk graphs in surfaces of constant curvature, i.e., on the sphere, flat torus, and especially hyperbolic surfaces. What is the size of the best clique-based separator for a uniform disk graph of radius $r$ on a hyperbolic surface of genus $g$?

Fourth, it would be interesting to investigate the complexity of problems other than Independent Set, and study how their complexity scales with the radius of the disks, or equivalently, with the curvature of the underlying space.

Finally, it is unclear whether our bound on balanced separators is tight for all values of $r$. For constant $r$, regular hyperbolic tilings are hyperbolic uniform disk graphs with constant clique number and logarithmic treewidth, making our bound asymptotically tight. However, for larger radii, it could be possible to reduce the logarithmic factor.