Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings

Abstract

Hyperbolic tilings are natural infinite planar graphs where each vertex has degree $q$ and each face has $p$ edges for some $\frac{1}{p}+\frac{1}{q}<\frac{1}{2}$. We study the structure of shortest paths in such graphs. We show that given a set of $n$ terminals, we can compute a so-called isometric closure (closely related to the geodesic convex hull) of the terminals in near-linear time, using a classic geometric convex hull algorithm as a black box. We show that the size of the convex hull is $O(N)$ where $N$ is the total length of the paths to the terminals from a fixed origin. Furthermore, we prove that the geodesic convex hull of a set of $n$ terminals has treewidth only $\max (12,O(\log \frac{n}{p+q}))$, a bound independent of the distance of the points involved. As a consequence, we obtain algorithms for subset TSP and Steiner tree with running time $O(N\log N)+\mathrm{poly}(\frac{n}{p+q})\cdot N$.