Relaxed gabriel graphs
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).
|Conference||21st Annual Canadian Conference on Computational Geometry, CCCG 2009|
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.