On a family of strong geometric spanners that admit local routing strategies

We introduce a family of directed geometric graphs, denoted G λ θ, that depend on two parameters λ and θ. For 0 < θ < π/2 and 1/2 < λ < 1, the Gλ θ graph is a strong t-spanner, with t = 1/(1-λ) cos θ. The out-degree of a node in the G λ θ graph is at most ⌊2π/ min(θ, arceos 1/2λ)⌋. Moreover, we show that routing can be achieved locally on Gλ θ. Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters λ and θ indicate that for random point sets, the spanning ratio of Gλ θ is better than the proven theoretical bounds