In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, 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

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 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

Line segment

In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...

 PQ is a diameter

Diameter

In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...

 contains no other elements of S. Gabriel graphs generalize to higher dimensions trivially, with the empty disks replaced by empty closed balls

Ball (mathematics)

In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....

. Gabriel graphs are named after K. R. Gabriel, who introduced them in a paper with R. R. Sokal

Robert R. Sokal

Robert Reuven Sokal is an Austrian-American biostatistician and anthropologist. Distinguished Professor Emeritus at the State University of Stony Brook, New York, Sokal is a member of the National Academy of Sciences and the American Academy of Arts and Sciences...

 in 1969.

The Gabriel graph is a subgraph of the Delaunay triangulation

Delaunay triangulation

In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...

; 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

Euclidean minimum spanning tree

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...

, the relative neighborhood graph

Relative neighborhood graph

In computational geometry, the relative neighborhood graph is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to both p and q than they are to each other...

, and the nearest neighbor graph

Nearest neighbor graph

The nearest neighbor graph for a set of n objects P in a metric space is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points...

. It is an instance of a beta-skeleton.