Proximity graphs represent neighbour relationships between objects (here geometric points in the Euclidean plane), although
analogies can be made with houses in the countryside, as above, for instance.
Given a set of points in the plane, put edges
between those points that satisfy a particular neighbour relationship with each other to form a graph. We will look at two
types of neighbourhood relations here, giving the Relative Neighbourhood and Gabriel proximity graphs. For both of these graphs we survey the
key properties, algorithms and embeddability results. For help visualizing all the graphs discussed here, there is a helpful applet
that displays the Minimum Spanning Tree (MST), the Delaunay Triangulation (DT), the Relative Neighbourhood Graph (RNG), and the Gabriel Graph
(GG) for an input point set. Proximity graphs have many applications, in particular, here we
discuss the application to prototype selection and hint at the scope of the other existing applications.
The Relative Neighbourhood Graph was introduced by Godfried Toussaint in an award-winning paper in 1980. Since, extensive
research has been done on this graph and its relatives and diverse applications have been proposed.
Next to Useful Graphs