A relative neighborhood graph is an undirected graph on a finite set of points in a metric space. Two distinct vertices and are joined by an edge iff no third point of the set is strictly closer to both and than they are to each other. Thus, with metric , a third point rules out the edge exactly when

For points in the Euclidean plane with Euclidean distance, this gives the original construction of Toussaint (1980). The relative neighborhood graph contains every Euclidean minimum spanning tree on the same point set and is a subgraph of the Gabriel graph. Drawing its edges as line segments therefore gives a plane graph.

Under the Manhattan distance, the four points , , , and all have pairwise distance 2. Every pair therefore forms an edge, giving the complete graph . Although is a planar graph, the horizontal and vertical edges cross at the origin in this straight-line drawing (Böltz 2026, pp. 35-36).

See also

Gabriel Graph, Metric Space, Minimum Spanning Tree, Plane Graph

Explore with Wolfram|Alpha

References

Böltz, L. M. Verification of Graph Algorithms in the Context of Wireless Networks. Koblenz, Germany: University of Koblenz, 2026. https://doi.org/10.82549/opus4-2740.Toussaint, G. T. "The Relative Neighbourhood Graph of a Finite Planar Set." Pattern Recognit. 12, 261-268, 1980. https://doi.org/10.1016/0031-3203(80)90066-7.

Cite this as:

Weisstein, Eric W. "Relative Neighborhood Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RelativeNeighborhoodGraph.html

Subject classifications