2026-07-26T03:03:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24240 2025-11-12T13:39:18Z ddc:004 open_access

Online Routing in Directed Yao₄^∞ Graphs Bose, Prosenjit De Carufel, Jean-Lou Stuart, John Geometric Spanners Yao Graphs Local Routing Algorithms The x⃑{Yao₄^∞} and x⃑{Yao₄} graphs are two families of directed geometric graphs whose vertices are points in the plane, and each vertex has up to four outgoing edges. Consider a horizontal and a vertical line through each vertex v, defining four quadrants around v. Then v has an outgoing edge to the closest vertex in each of its four quadrants. When the distance is measured using the Euclidean norm, the resulting graph is the x⃑{Yao₄} graph, whereas with the L_∞-norm, we obtain the x⃑{Yao^{∞}₄} graph, which is a sub-graph of the well-known L_∞-Delaunay graph. In this paper, we provide a local routing algorithm with routing ratio at most 85.22 for x⃑{Yao^{∞}₄} graphs. Prior to this work, no constant spanning or routing ratios for x⃑{Yao₄^∞} graphs were previously known. Now, x⃑{Yao₄^∞} graphs are the sparsest family of directed planar graphs supporting a competitive local routing strategy. Furthermore, we show that no local routing algorithm for x⃑{Yao₄^∞} graphs can have a routing ratio lower than 7+√2≈ 8.41. Moreover, we prove that the spanning ratio is at least 5+√2≈ 6.41 in the worst case. The techniques we develop in this paper also allow us to prove lower bounds of 7-√3+√{5-2√3}≈ 6.51 and 7+√2 for the spanning and routing ratios of x⃑{Yao₄}, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Jean-Lou De Carufel and John Stuart 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.9 urn:nbn:de:0030-drops-242404 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode