# Gabriel graph 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 and computational geometry, 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 $G$ with vertex set $S$ in which any points $p\in S$ and $q\in S$ are adjacent precisely if they are distinct, i.e. $p\neq q$ , and the closed disc of which line segment ${\overline {pq}}$ is a diameter contains no other elements of $S$ . Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.

## Percolation

A finite site percolation threshold for Gabriel graphs has been proven to exist by Bertin, Billiot & Drouilhet (2002), and more precise values of both site and bond thresholds have been given by Norrenbrock (2014).

## Related geometric graphs

The Gabriel graph is a subgraph of the Delaunay triangulation. It can be found in linear time if the Delaunay triangulation is given (Matula & Sokal 1980).

The Gabriel graph contains, as subgraphs, the Euclidean minimum spanning tree, the relative neighborhood graph, and the nearest neighbor graph.

It is an instance of a beta-skeleton. Like beta-skeletons, and unlike Delaunay triangulations, it is not a geometric spanner: for some point sets, distances within the Gabriel graph can be much larger than the Euclidean distances between points (Bose et al. 2006).