Dumitrescu, Adrian ;
Ghosh, Anirban ;
Tóth, Csaba D.
Sparse Hop Spanners for Unit Disk Graphs
Abstract
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 ∈ P if and only if pq ≤ 1. A subgraph G' of G is a khop spanner if and only if for every edge pq ∈ G, the topological shortest path between p,q in G' has at most k edges. We obtain the following results for unit disk graphs.
1) Every nvertex unit disk graph has a 5hop 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.
2) Using a new construction, we show that every nvertex unit disk graph has a 3hop spanner with at most 11n edges.
3) Every nvertex unit disk graph has a 2hop spanner with O(nlog n) edges. This is the first nontrivial construction of 2hop spanners.
4) 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.
5) For every point set on a circle, there exists a plane 4hop spanner. As such, this provides a tight bound for points on a circle.
6) The maximum degree of khop spanners cannot be bounded from above by a function of k.
BibTeX  Entry
@InProceedings{dumitrescu_et_al:LIPIcs:2020:13401,
author = {Adrian Dumitrescu and Anirban Ghosh and Csaba D. T{\'o}th},
title = {{Sparse Hop Spanners for Unit Disk Graphs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {57:157:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13401},
URN = {urn:nbn:de:0030drops134018},
doi = {10.4230/LIPIcs.ISAAC.2020.57},
annote = {Keywords: graph approximation, εnet, hopspanner, unit disk graph, lower bound}
}
04.12.2020
Keywords: 

graph approximation, εnet, hopspanner, unit disk graph, lower bound 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 