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).
