arXiv preprint ·
Navigable Graphs for Low-Dimensional Hyperbolic Spaces
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $Ω(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 $Ω(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 $α>1$, an $α$-navigable graph may require $Ω(n^2)$ edges, which rules out the standard route of using $α$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $Ω(\log n)$, there are point sets for which every navigable graph may require $n^{3/2-o(1)}$ edges, matching the upper bounds for general metrics.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Linear Time Maximum Clique in Circular Arc Graphs
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
Splitting Planar Necklaces with Few Straight Cuts
Online geometric matching and segments block points
A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.