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.

Additional Metadata
Citation
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Smid, M, & Xu, D. (Darning). (2007). On a family of strong geometric spanners that admit local routing strategies.