A Gabriel graph is an undirected graph on a point set in the Euclidean
plane. Two distinct vertices 
and 
are joined by an edge iff
the closed disk with diameter 
contains no other point
of the set (Gabriel and Sokal 1969, Matula and Sokal 1980).
Drawing each edge as a line segment gives a plane graph. The relative neighborhood graph on the same vertex set is a subgraph of the Gabriel graph because any third point in the closed disk is strictly closer to each endpoint than the endpoints are to each other. For a noncollinear point set, the Gabriel graph is in turn a subgraph of the Delaunay triangulation. The midpoint of each Gabriel edge is strictly closer to its two endpoints than to any other point, so the two corresponding cells of the Voronoi diagram share a line segment of positive length.
