# Local Routing in Sparse and Lightweight Geometric Graphs

arXiv: https://arxiv.org/abs/1909.10215 · HTML: https://mlsanity.com/paper/1909.10215/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Bridging Local and Global Knowledge: Cascaded Mixture-of-Experts Learning for Near-Shortest Path Routing](https://mlsanity.com/paper/2603.15541/) (2026)

## Abstract (arXiv)

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.