We study a new family of geometric graphs that interpolate between the Delaunay triangulation and the Gabriel graph. These graphs share many properties with β- skeletons for β ε 2 [0; 1] (such as sublinear spanning ratio) with the added benefit of planarity (and consequently linear size and local routability).

Additional Metadata
Conference 21st Annual Canadian Conference on Computational Geometry, CCCG 2009
Citation
Bose, P, Cardinal, J. (Jean), Collette, S. (Sébastien), Demaine, E.D. (Erik D.), Palop, B. (Belén), Taslakian, P. (Perouz), & Zehk, N. (Norbert). (2009). Relaxed gabriel graphs. Presented at the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009.