Relaxed gabriel graphs
Prosenjit K. Bose, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Belén Palop, Perouz Taslakian, Norbert Zeh · 2009
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 β ∈ [0, 1] (such as sublinear spanning ratio) with the added benefit of planarity (and consequently linear size and local routability). 1