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.16
URN: urn:nbn:de:0030-drops-133602
Go to the corresponding LIPIcs Volume Portal

Mulzer, Wolfgang ; Willert, Max

Compact Routing in Unit Disk Graphs

LIPIcs-ISAAC-2020-16.pdf (0.6 MB)


Let V ⊂ ℝ² be a set of n sites in the plane. The unit disk graph DG(V) of V is the graph with vertex set V where two sites v and w are adjacent if and only if their Euclidean distance is at most 1.
We develop a compact routing scheme ℛ for DG(V). The routing scheme ℛ preprocesses DG(V) by assigning a label 𝓁(v) to every site v in V. After that, for any two sites s and t, the scheme ℛ must be able to route a packet from s to t as follows: given the label of a current vertex r (initially, r = s), the label of the target vertex t, and additional information in the header of the packet, the scheme determines a neighbor r' of r. Then, the packet is forwarded to r', and the process continues until the packet reaches its desired target t. The resulting path between the source s and the target t is called the routing path of s and t. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in DG(V), between any two sites s, t ∈ V.
We show that for any given ε > 0, we can construct a routing scheme for DG(V) with diameter D that achieves stretch 1+ε, has label size (1/ε)^{O(ε^(-2))} log Dlog³n/log log n, and the header has at most O(log²n/log log n) bits. In the past, several routing schemes for unit disk graphs have been proposed. Our scheme achieves poly-logarithmic label and header size, small stretch and does not use any neighborhood oracles.

BibTeX - Entry

  author =	{Wolfgang Mulzer and Max Willert},
  title =	{{Compact Routing in Unit Disk Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{16:1--16:14},
  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 =		{},
  URN =		{urn:nbn:de:0030-drops-133602},
  doi =		{10.4230/LIPIcs.ISAAC.2020.16},
  annote =	{Keywords: routing scheme, unit disk graph, separator}

Keywords: routing scheme, unit disk graph, separator
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