Navigable Graphs for Low-Dimensional Hyperbolic Spaces

A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t\in P$, $s$ has an out-neighbor $v$ with $d(v,t)<d(s,t)$, so greedy routing always reaches the destination. Existing work on sparse navigable graphs mostly assumes bounded doubling dimensions. In this paper, we show that constant-dimensional hyperbolic spaces that do not have bounded doubling dimension also admit sparse navigable graphs. Specifically, for an $n$-point set in ${\mathbb{H}}^k$ with a constant $k$, we construct a navigable graph of size $O_k(n)$ with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every $n$-point set in ${\mathbb{H}}^k$ admits a navigable graph on the input points alone with $O_k(n)$ edges, though a single vertex may have out-degree $\mathrm{\Omega }(n)$. Furthermore, with a refined construction with $O_k(n\log n)$ edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected $O({\log }^{2}n)$ in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by $O_k(\log n)$. We complement these upper bounds with matching lower bound results. In the hyperbolic plane, there are point sets for which every navigable graph requires maximum out-degree $\mathrm{\Omega }(n)$, so the maximum linear out-degree above is unavoidable and constant out-degree is only possible with Steiner points. Next, we show that for every constant $\alpha >1$, an $\alpha$-navigable graph may require $\mathrm{\Omega }(n^2)$ edges, which rules out the standard route of using $\alpha$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $\mathrm{\Omega }(\log n)$, there are point sets for which every navigable graph may require $n^{3\mathrm{/}2-o(1)}$ edges, matching the upper bounds for general metrics.