Compact Routing in Unit Disk Graphs

Authors Wolfgang Mulzer , Max Willert



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.16.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, Germany
Max Willert
  • Institut für Informatik, Freie Universität Berlin, Germany

Cite AsGet BibTex

Wolfgang Mulzer and Max Willert. Compact Routing in Unit Disk Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.16

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • routing scheme
  • unit disk graph
  • separator

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In Proc. 25th Int. Symp. Dist. Comp. (DISC), pages 404-415, 2011. Google Scholar
  2. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS), page 75, 2006. Google Scholar
  3. Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307-341, 1990. Google Scholar
  4. Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert. Routing in polygonal domains. In Proc. 28th Annu. Internat. Sympos. Algorithms Comput. (ISAAC), pages 10:1-10:13, 2017. Google Scholar
  5. Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Sparse covers for planar graphs and graphs that exclude a fixed minor. Algorithmica, 69(3):658-684, 2014. Google Scholar
  6. Timothy M. Chan and Dimitrios Skrepetos. Approximate shortest paths and distance oracles in weighted unit-disk graphs. J. of Computational Geometry, 10(2):3-20, 2019. Google Scholar
  7. Shiri Chechik. Compact routing schemes with improved stretch. In Proc. ACM Symp. Princ. Dist. Comp. (PODC), pages 33-41, 2013. Google Scholar
  8. Brent N Clark, Charles J Colbourn, and David S Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. Google Scholar
  9. Lenore J Cowen. Compact routing with minimum stretch. J. Algorithms, 38(1):170-183, 2001. Google Scholar
  10. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. J. Algorithms, 46(2):97-114, 2003. Google Scholar
  11. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Proc. 28th Internat. Colloq. Automata Lang. Program. (ICALP), pages 757-772, 2001. Google Scholar
  12. Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In Proc. 19th Sympos. Theoret. Aspects Comput. Sci. (STACS), pages 65-75, 2002. Google Scholar
  13. Silvia Giordano and Ivan Stojmenovic. Position based routing algorithms for ad hoc networks: A taxonomy. In Ad hoc wireless networking, pages 103-136. Springer-Verlag, 2004. Google Scholar
  14. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs. Algorithmica, 80(3):830-848, 2018. Google Scholar
  15. Goran Konjevod, Andréa W Richa, and Donglin Xia. Scale-free compact routing schemes in networks of low doubling dimension. ACM Trans. Algorithms, 12(3):1-29, 2016. Google Scholar
  16. Xiang-Yang Li, Gruia Calinescu, and Peng-Jun Wan. Distributed construction of a planar spanner and routing for ad hoc wireless networks. In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1268-1277. IEEE, 2002. Google Scholar
  17. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510-530, 1989. Google Scholar
  18. Liam Roditty and Roei Tov. New routing techniques and their applications. In Proc. ACM Symp. Princ. Dist. Comp. (PODC), pages 23-32, 2015. Google Scholar
  19. Liam Roditty and Roei Tov. Close to linear space routing schemes. Distributed Computing, 29(1):65-74, 2016. Google Scholar
  20. Nicola Santoro and Ramez Khatib. Labelling and implicit routing in networks. The Computer Journal, 28(1):5-8, 1985. Google Scholar
  21. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. Google Scholar
  22. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proc. 13th ACM Symp. Par. Algo. Arch. (SPAA), pages 1-10, 2001. Google Scholar
  23. Max Willert. Routing schemes for disk graphs and polygons. Master’s thesis, Freie Universität Berlin, 2016. Google Scholar
  24. Chenyu Yan, Yang Xiang, and Feodor F Dragan. Compact and low delay routing labeling scheme for unit disk graphs. Comput. Geom. Theory Appl., 45(7):305-325, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail