Sparse hop spanners for unit disk graphs

Publication date 15 December 2021

Abstract: A unit disk graph

G

on a given set

P

of points in the plane is a geometric graph where an edge exists between two points

p, q i n P

if and only if

| p q | l e q 1

. A spanning subgraph

G^{'}

of

G

is a

k

-hop spanner if and only if for every edge

p q i n G

, there is a path between

p, q

in

G^{'}

with at most

k

edges. We obtain the following results for unit disk graphs in the plane. (I) Every

n

-vertex unit disk graph has a

5

-hop spanner with at most

5.5 n

edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from

9 n

to

5.5 n

. (II) Using a new construction, we show that every

n

-vertex unit disk graph has a

3

-hop spanner with at most

11 n

edges. (III) Every

n

-vertex unit disk graph has a

2

-hop spanner with

O (n l o g n)

edges. This is the first nontrivial construction of

2

-hop spanners. (IV) For every sufficiently large positive integer

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 finite point set on a circle, there exists a plane (i.e., crossing-free)

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

for any positive integer

k

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Sparse hop spanners for unit disk graphs