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