2026-07-23T20:32:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17665 2024-03-06T11:00:15Z ddc:004 open_access

Strongly Hyperbolic Unit Disk Graphs Bläsius, Thomas Friedrich, Tobias Katzmann, Maximilian Stephan, Daniel hyperbolic geometry unit disk graphs greedy routing hyperbolic random graphs graph classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Bläsius and Tobias Friedrich and Maximilian Katzmann and Daniel Stephan 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.13 urn:nbn:de:0030-drops-176652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.13 eng https://creativecommons.org/licenses/by/4.0/legalcode