Structure and Independence in Hyperbolic Uniform Disk Graphs

We consider intersection graphs of disks of radius $r$ in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of $r$, where very small $r$ corresponds to an almost-Euclidean setting and $r\in \mathrm{\Omega }(\log n)$ corresponds to a firmly hyperbolic setting. We observe that larger values of $r$ create simpler graph classes, at least in terms of separators and the computational complexity of the $\text{textsc}IndependentSet$ problem. First, we show that intersection graphs of disks of radius $r$ in the hyperbolic plane can be separated with $\mathcal{O}((1+1\mathrm{/}r)\log n)$ cliques in a balanced manner. Our second structural insight concerns Delaunay complexes in the hyperbolic plane and may be of independent interest. We show that for any set $S$ of $n$ points with pairwise distance at least $2r$ in the hyperbolic plane the corresponding Delaunay complex has outerplanarity $1+\mathcal{O}(\frac{\log n}{r})$, which implies a similar bound on the balanced separators and treewidth of such Delaunay complexes. Using this outerplanarity (and treewidth) bound we prove that $\text{textsc}IndependentSet$ can be solved in $n^{\mathcal{O}(1+\frac{\log n}{r})}$ time. The algorithm is based on dynamic programming on some unknown sphere cut decomposition that is based on the solution. The resulting algorithm is a far-reaching generalization of a result of Kisfaludi-Bak (SODA 2020), and it is tight under the Exponential Time Hypothesis. In particular, $\text{textsc}IndependentSet$ is polynomial-time solvable in the firmly hyperbolic setting of $r\in \mathrm{\Omega }(\log n)$. Finally, in the case when the disks have ply (depth) at most $\mathrm{\ell }$, we give a PTAS for $\text{textsc}MaximumIndependentSet$ that has only quasi-polynomial dependence on $1\mathrm{/}\epsilon$ and $\mathrm{\ell }$. Our PTAS is a further generalization of our exact algorithm.