Search Results

Documents authored by Chiu, Yu-Cheng

Document
DOI: 10.4230/LIPIcs.WG.2026.12
Geometric Routing in Geometric Inhomogeneous Random Graphs

Authors: Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis, and Ulysse Schaller

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol. While greedy routing in GIRGs is known to explain the algorithmic small-world phenomenon by finding ultra-short paths of length Θ(log log n), it assumes additional knowledge of vertex weights beyond geometry, an assumption that is often restrictive or unavailable. We investigate whether the underlying geometry alone is sufficient for efficient navigation. We prove that for power-law weight exponent τ ∈ (2,3) and geometric decay parameter α > τ-1, geometric routing succeeds with constant probability and finds ultra-short paths of length Θ(log log n), matching the optimal asymptotic guarantees for greedy routing. Our analysis further reveals that, upon success, both protocols follow a similar two-phase trajectory, consisting of a rapid ascent to the heavy vertices, followed by efficient navigation to the target. These results demonstrate that, in the appropriate regime, the network’s geometry alone implicitly guides the path to the target through its high-weight core.
Cite as

Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis, and Ulysse Schaller. Geometric Routing in Geometric Inhomogeneous Random Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.WG.2026.12,
  author =	{Chiu, Yu-Cheng and Kaufmann, Marc and Lakis, Kostas and Schaller, Ulysse},
  title =	{{Geometric Routing in Geometric Inhomogeneous Random Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.12},
  URN =		{urn:nbn:de:0030-drops-261780},
  doi =		{10.4230/LIPIcs.WG.2026.12},
  annote =	{Keywords: geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs (HRGs), greedy routing, geometric routing, navigability, small-world phenomenon, decentralized algorithms}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact