Local routing on ordered Θ-graphs

The problem of locally routing on geometric networks using limited memory is extensively studied in computational geometry. We consider one particular graph, the ordered Θ-graph, which is significantly harder to route on than the Θ-graph, for which a number of routing algorithms are known. Currently, no local routing algorithm is known for the ordered Θ-graph. We prove that, unfortunately, there does not exist a deterministic memoryless local routing algorithm that works on the ordered Θ-graph. This motivates us to consider allowing a small amount of memory, and we present a deterministic O (1)-memory local routing algorithm that successfully routes from the source to the destination on the ordered Θ-graph. We show that our local routing algorithm converges to the destination in O ( n ) hops, where n is the number of vertices. To the best of our knowledge, our algorithm is the first deterministic local routing algorithm that is guaranteed to reach the destination on the ordered Θ-graph.