pipette
ENEnglish

Navigable Graphs for Low-Dimensional Hyperbolic Spaces

Chengyuan Deng, Jie Gao, Kuijun Liu, Kevin Lu, Feng Luo, Puheng Weng, Cheng Xin

Preprint

En palabras de los autores

A directed graph on a point set in a metric space is navigable if for every ordered pair of distinct points , has an out-neighbor with , 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 -point set in with a constant , we construct a navigable graph of size with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every -point set in admits a navigable graph on the input points alone with edges, though a single vertex may have out-degree . Furthermore, with a refined construction with edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by . 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 , 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 , an -navigable graph may require edges, which rules out the standard route of using -navigability to obtain greedy paths of bounded hops. Last, once the dimension reaches , there are point sets for which every navigable graph may require edges, matching the upper bounds for general metrics.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.