# Gabriel graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Gabriel_graph
> Markdown URL: https://mediated.wiki/source/Gabriel_graph.md
> Source: https://en.wikipedia.org/wiki/Gabriel_graph
> Source revision: 1329248579
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Graph defined from a set of points in the Euclidean plane}}
{{multiple image
| total_width       = 400
| image1            = Gabriel Pairs.svg
| caption1          = Points <math>a</math> and <math>b</math> are Gabriel neighbours, as <math>c</math> is outside their diameter circle.
| image2            = Not Gabriel Pairs.svg
| caption2          = The presence of point <math>c</math> within the circle prevents points <math>a</math> and <math>b</math> from being Gabriel neighbors.
}}
thumb|The Gabriel graph of 100 random points
In [mathematics](/source/mathematics) and [computational geometry](/source/computational_geometry), the '''Gabriel graph''' of a [set](/source/set_(mathematics)) <math>S</math> of points in the [Euclidean plane](/source/Euclidean_plane) expresses one notion of proximity or nearness of those points.  Formally, it is the [graph](/source/Graph_(discrete_mathematics)) <math>G</math> with vertex set <math>S</math> in which any two distinct points <math>p \in S</math> and <math>q \in S</math> are adjacent precisely when the closed [disc](/source/disc_(mathematics)) having <math>pq</math> as a [diameter](/source/diameter) contains no other points. Another way of expressing the same adjacency criterion is that <math>p</math> and <math>q</math> should be the two closest given points to their [midpoint](/source/midpoint), with no other given point being as close. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed [balls](/source/ball_(mathematics)). Gabriel graphs are named after [K. Ruben Gabriel](/source/K._Ruben_Gabriel), who introduced them in a paper with [Robert R. Sokal](/source/Robert_R._Sokal) in 1969.{{r|gabsok}}

==Percolation==
For Gabriel graphs of infinite random point sets, the finite site [percolation threshold](/source/percolation_threshold) gives the fraction of points needed to support connectivity: if a random subset of fewer vertices than the threshold is given, the remaining graph will almost surely have only finite connected components, while if the size of the random subset is more than the threshold, then the remaining graph will almost surely have an infinite component (as well as finite components). This threshold was proved to exist by {{harvtxt|Bertin|Billiot|Drouilhet|2002}},{{r|bbd}} and more precise values of both site and bond thresholds have been given by Norrenbrock.{{r|nor}}

==Related geometric graphs==
The Gabriel graph is a [subgraph](/source/Glossary_of_graph_theory) of the [Delaunay triangulation](/source/Delaunay_triangulation). It can be found in [linear time](/source/linear_time) if the Delaunay triangulation is given.{{r|matsok}}

The Gabriel graph contains, as subgraphs, the [Euclidean minimum spanning tree](/source/Euclidean_minimum_spanning_tree), the [relative neighborhood graph](/source/relative_neighborhood_graph), and the [nearest neighbor graph](/source/nearest_neighbor_graph).

It is an instance of a [beta-skeleton](/source/beta-skeleton). Like beta-skeletons, and unlike Delaunay triangulations, it is not a [geometric spanner](/source/geometric_spanner): for some point sets, distances within the Gabriel graph can be much larger than the Euclidean distances between points.{{r|bdek}}

== References ==
<references>

<ref name=bbd>{{citation
 | last1 = Bertin | first1 = Etienne
 | last2 = Billiot | first2 = Jean-Michel
 | last3 = Drouilhet | first3 = Rémy
 | doi = 10.1239/aap/1037990948
 | issue = 4
 | journal = [Advances in Applied Probability](/source/Advances_in_Applied_Probability)
 | mr = 1938937
 | pages = 689–701
 | title = Continuum percolation in the Gabriel graph
 | volume = 34
 | year = 2002| s2cid = 121288601
 }}</ref>

<ref name=bdek>{{citation
 | last1 = Bose | first1 = Prosenjit | author1-link = Jit Bose
 | last2 = Devroye | first2 = Luc | author2-link = Luc Devroye
 | last3 = Evans | first3 = William
 | last4 = Kirkpatrick | first4 = David | author4-link = David G. Kirkpatrick
 | doi = 10.1137/S0895480197318088
 | issue = 2
 | journal = [SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)
 | mr = 2257270
 | pages = 412–427
 | title = On the spanning ratio of Gabriel graphs and β-skeletons
 | volume = 20
 | year = 2006| citeseerx = 10.1.1.46.4728}}</ref>

<ref name=gabsok>{{citation
 | last1 = Gabriel | first1 = K. Ruben | author1-link = K. Ruben Gabriel
 | last2 = Sokal | first2 = Robert R. | author2-link = Robert R. Sokal
 | title = A new statistical approach to geographic variation analysis
 | journal = [Systematic Biology](/source/Systematic_Biology)
 | year = 1969
 | pages = 259–278
 | volume = 18
 | doi = 10.2307/2412323
 | jstor = 2412323
 | issue = 3}}</ref>

<ref name=matsok>{{citation
 | last1 = Matula | first1 = David W. | author1-link = David Matula
 | last2 = Sokal | first2 = Robert R. | author2-link = Robert R. Sokal
 | doi = 10.1111/j.1538-4632.1980.tb00031.x | doi-access = free
 | title = Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane
 | journal = Geographical Analysis
 | year = 1980
 | pages = 205–222
 | issue = 3
 | volume = 12}}</ref>

<ref name=nor>{{citation
 | last = Norrenbrock | first = Christoph
 | arxiv = 1406.0663
 | date = May 2016
 | doi = 10.1140/epjb/e2016-60728-0
 | issue = 5
 | journal = [European Physical Journal B](/source/European_Physical_Journal_B)
 | title = Percolation threshold on planar Euclidean Gabriel graphs
 | volume = 89| page = 111
 | bibcode = 2016EPJB...89..111N
 | s2cid = 254114033
 }}</ref>

</references>

Category:Euclidean plane geometry
Category:Geometric graphs

---
Adapted from the Wikipedia article [Gabriel graph](https://en.wikipedia.org/wiki/Gabriel_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Gabriel_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.