Document Open Access Logo

Strongly Hyperbolic Unit Disk Graphs

Authors Thomas Bläsius , Tobias Friedrich , Maximilian Katzmann , Daniel Stephan

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.13.pdf
  • Filesize: 1.11 MB
  • 17 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Maximilian Katzmann
  • Karlsruhe Institute of Technology, Germany
Daniel Stephan
  • GSV Algorithm Consulting UG (haftungsbeschränkt) & Co. KG, Potsdam, Germany

Funding

This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Grant No. 390859508.

Cite AsGet BibTex

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly Hyperbolic Unit Disk Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.13

Abstract

The class of Euclidean unit disk graphs is one of the most fundamental and well-studied graph classes with underlying geometry. In this paper, we identify this class as a special case in the broader class of hyperbolic unit disk graphs and introduce strongly hyperbolic unit disk graphs as a natural counterpart to the Euclidean variant. In contrast to the grid-like structures exhibited by Euclidean unit disk graphs, strongly hyperbolic networks feature hierarchical structures, which are also observed in complex real-world networks. We investigate basic properties of strongly hyperbolic unit disk graphs, including adjacencies and the formation of cliques, and utilize the derived insights to demonstrate that the class is useful for the development and analysis of graph algorithms. Specifically, we develop a simple greedy routing scheme and analyze its performance on strongly hyperbolic unit disk graphs in order to prove that routing can be performed more efficiently on such networks than in general.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
Keywords
  • hyperbolic geometry
  • unit disk graphs
  • greedy routing
  • hyperbolic random graphs
  • graph classes

Metrics

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

Related Versions

References

  1. Baruch Awerbuch, Shay Kutten, and David Peleg. On buffer-economical store-and-forward deadlock prevention. IEEE Transactions on Communications, 42(11):2934-2937, 1994. URL: https://doi.org/10.1109/26.328973.
  2. Baruch Awerbuch and David Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discrete Math., 5:151-162, May 1992. URL: https://doi.org/10.1137/0405013.
  3. Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly hyperbolic unit disk graphs. CoRR, abs/2107.05518, 2021. URL: http://arxiv.org/abs/2107.05518.
  4. Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1(1):62, 2010. URL: https://doi.org/10.1038/ncomms1063.
  5. Leizhen Cai. NP-completeness of minimum spanner problems. Discrete Applied Mathematics, 48(2):187-194, 1994. URL: https://doi.org/10.1016/0166-218X(94)90073-6.
  6. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. URL: https://doi.org/10.1016/0012-365X(90)90358-O.
  7. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210-236, 1998. URL: https://doi.org/10.1137/S0097539794261295.
  8. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46(2):97-114, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00002-6.
  9. R. Flury, S. V. Pemmaraju, and R. Wattenhofer. Greedy routing with bounded stretch. In IEEE INFOCOM 2009, pages 1737-1745, 2009. URL: https://doi.org/10.1109/INFCOM.2009.5062093.
  10. Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson, and Oren Weimann. Optimal distance labeling schemes for trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 185-194, 2017. URL: https://doi.org/10.1145/3087801.3087804.
  11. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. URL: https://doi.org/10.1016/j.jalgor.2004.05.002.
  12. Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 125-133, 1996. URL: https://doi.org/10.1145/248052.248075.
  13. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: degree sequence and clustering. In International Colloquium on Automata, Languages, and Programming, pages 573-585. Springer, 2012. Google Scholar
  14. R. Houthooft, S. Sahhaf, W. Tavernier, F. De Turck, D. Colle, and M. Pickavet. Fault-tolerant greedy forest routing for complex networks. In 2014 6th International Workshop on Reliable Networks Design and Modeling (RNDM), pages 1-8, 2014. URL: https://doi.org/10.1109/RNDM.2014.7014924.
  15. M.L. Huson and A. Sen. Broadcast scheduling algorithms for radio networks. In Proceedings of MILCOM '95, volume 2, pages 647-651 vol.2, 1995. URL: https://doi.org/10.1109/MILCOM.1995.483546.
  16. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs. Algorithmica, 80(3):830-848, 2018. URL: https://doi.org/10.1007/s00453-017-0308-2.
  17. Sándor Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Symposium on Discrete Algorithms (SODA), pages 1621-1638, 2020. URL: https://doi.org/10.1137/1.9781611975994.100.
  18. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  19. Anton Krohmer. Structures & Algorithms in Hyperbolic Random Graphs. Doctoral thesis, Universität Potsdam, 2016. Google Scholar
  20. Tobias Müller and Merlijn Staps. The diameter of kpkvb random graphs. Advances in Applied Probability, 51(2):358-377, 2019. URL: https://doi.org/10.1017/apr.2019.23.
  21. F. Papadopoulos, D. Krioukov, M. Boguna, and A. Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In 2010 Proceedings IEEE INFOCOM, pages 1-9, 2010. URL: https://doi.org/10.1109/INFCOM.2010.5462131.
  22. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
  23. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510-530, 1989. URL: https://doi.org/10.1145/65950.65953.
  24. Vijay Raghavan and Jeremy Spinrad. Robust algorithms for restricted domains. Journal of Algorithms, 48(1):160-172, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00048-8.
  25. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: http://networkrepository.com.
  26. M. Tang, H. Chen, G. Zhang, and J. Yang. Tree cover based geographic routing with guaranteed delivery. In 2010 IEEE International Conference on Communications, pages 1-5, 2010. URL: https://doi.org/10.1109/ICC.2010.5502391.
  27. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 1-10, 2001. URL: https://doi.org/10.1145/378580.378581.
  28. Huaming Zhang and Swetha Govindaiah. Greedy routing via embedding graphs onto semi-metric spaces. Theoretical Computer Science, 508:26-34, 2013. URL: https://doi.org/10.1016/j.tcs.2012.01.049.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact