Details

Routing In Greedy Spanners

Year: 2026

Term: Winter

Student Name: Marco Toito

Supervisor: Prosenjit Bose

Abstract: Geometric routing studies algorithms that use only local information to route efficiently in geometric graphs. Graph spanners, particularly greedy spanners, are well-suited for this problem due to their strong properties, including low stretch, sparsity, and lightness. However, these properties do not guarantee that simple local routing algorithms will succeed. In this report, I investigate routing algorithms on greedy spanners, including greedy routing and compass routing, and show that purely memoryless approaches can fail to guarantee delivery. I also examine routing on the minimum spanning tree, which ensures success but produces inefficient paths. To address this tradeoff, I propose a clustered spanner routing algorithm that combines local routing with MST-based fallback. The algorithm organizes the graph into clusters and routes in multiple phases. Experimental results show that it guarantees delivery while improving path quality over MST routing. This work introduces a hierarchical perspective for routing on greedy spanners as a direction for further improvement.