License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.57
URN: urn:nbn:de:0030-drops-134018
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13401/
Go to the corresponding LIPIcs Volume Portal

Dumitrescu, Adrian ; Ghosh, Anirban ; Tóth, Csaba D.

Sparse Hop Spanners for Unit Disk Graphs

pdf-format:
LIPIcs-ISAAC-2020-57.pdf (0.7 MB)

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 k-hop 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 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.
2) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges.
3) Every n-vertex unit disk graph has a 2-hop spanner with O(nlog n) edges. This is the first nontrivial construction of 2-hop 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 4-hop spanner. As such, this provides a tight bound for points on a circle.
6) The maximum degree of k-hop 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:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13401},
  URN =		{urn:nbn:de:0030-drops-134018},
  doi =		{10.4230/LIPIcs.ISAAC.2020.57},
  annote =	{Keywords: graph approximation, ε-net, hop-spanner, unit disk graph, lower bound}
}

Keywords: graph approximation, ε-net, hop-spanner, unit disk graph, lower bound
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI