Sparse Hop Spanners for Unit Disk Graphs

A unit disk graph $G$ on a given set of points $P$ in the plane is a geometric graph where an edge exists between two points $p,q \in P$ if and only if $|pq| \leq 1$. A subgraph $G'$ of $G$ is a \emph{$k$-hop spanner} if and only if for every edge $pq\in G$, the topological shortest path between $p,q$ in $G'$ has at most $k$ edges. We obtain the following results for unit disk graphs. (I) Every $n$-vertex unit disk graph has a $5$-hop spanner with at most $5.5n$ edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from $9n$ to $5.5n$. (II) Using a new construction, we show that every $n$-vertex unit disk graph has a $3$-hop spanner with at most $11n$ edges. (III) Every $n$-vertex unit disk graph has a $2$-hop spanner with $O(n\log n)$ edges. This is the first nontrivial construction of $2$-hop spanners. (IV) For every sufficiently large $n$, there exists a set $P$ of $n$ points on a circle, such that every plane hop spanner on $P$ has hop stretch factor at least $4$. Previously, no lower bound greater than $2$ was known. (V) For every point set on a circle, there exists a plane $4$-hop spanner. As such, this provides a tight bound for points on a circle. (VI) The maximum degree of $k$-hop spanners cannot be bounded from above by a function of~$k$.