Gabriel graph

The Gabriel graph of 100 random points

Points a and b are Gabriel neighbours, as c is outside their diameter circle.

The presence of point c within the circle prevents points a and b from being Gabriel neighbors.

In mathematics, the Gabriel graph of a set S of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set S in which any points P and Q in S are adjacent precisely if they are distinct and the closed disc of which line segment PQ is a diameter contains no other elements of S. Gabriel graphs generalize to higher dimensions trivially, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. R. Gabriel, who introduced them in a paper with R. R. Sokal in 1969.

The Gabriel graph is a subgraph of the Delaunay triangulation; it can be found in linear time if the Delaunay triangulation is given (Matula and Sokal, 1980). The Gabriel graph contains as a subgraph the Euclidean minimum spanning tree, the relative neighborhood graph, and the nearest neighbor graph. It is an instance of a beta-skeleton.

References

• Gabriel, K. R.; Sokal, R. R. (1969), "A new statistical approach to geographic variation analysis", Systematic Zoology (Society of Systematic Biologists) 18 (3): 259–270, doi:10.2307/2412323, JSTOR 2412323 .
• Matula, D. W.; Sokal, R. R. (1980), "Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane", Geogr. Anal. 12 (3): 205–222, doi:10.1111/j.1538-4632.1980.tb00031.x .