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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13360/
Mulzer, Wolfgang ;
Willert, Max
Compact Routing in Unit Disk Graphs
Abstract
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
@InProceedings{mulzer_et_al:LIPIcs:2020:13360,
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 = {https://drops.dagstuhl.de/opus/volltexte/2020/13360},
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 |
