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 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 ( WADS 2019 ) 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 ^{3/2 ) edges. This is the first construction of a 2-hop spanner with a subquadratic number of edges. (iv ) For every sufficiently large n, there exists a set P of n points  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  above by a function of  k.
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 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.
R
k-hop spanner
k-hop spanner
R
i
I
R
WADS 2019
2020
R
ii
II
R
iii
III
R
^{3/2
\log n
R
construction of a
nontrivial construction of
R
spanner with a subquadratic number of edges. (iv
spanners. (IV
A
on a circle,
R
v
V
R
vi
VI
A
from
A
~