Gabriel graph

Jump to navigation Jump to search
The Gabriel graph of 100 random points
Points ${\displaystyle a}$ and ${\displaystyle b}$ are Gabriel neighbours, as ${\displaystyle c}$ is outside their diameter circle.
The presence of point ${\displaystyle c}$ within the circle prevents points ${\displaystyle a}$ and ${\displaystyle b}$ from being Gabriel neighbors.

In mathematics and computational geometry, the Gabriel graph of a set ${\displaystyle S}$ of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph ${\displaystyle G}$ with vertex set ${\displaystyle S}$ in which any points ${\displaystyle p\in S}$ and ${\displaystyle q\in S}$ are adjacent precisely if they are distinct, i.e. ${\displaystyle p\neq q}$, and the closed disc of which line segment ${\displaystyle {\overline {pq}}}$ is a diameter contains no other elements of ${\displaystyle S}$. Gabriel graphs naturally generalize to higher dimensions, 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.

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).