Relative neighborhood graph

In computational geometry, the relative neighborhood graph (RNG) was proposed by Godfried Toussaint in 1980. There has been a lot of research on this kind of graph.

Definition

The relative neighborhood graph of a graph G = (V, E), denoted by RNG(G), is the set of all edges uv є E such that there is no vertex or point w where uw є E, wv є E and ||uw|| < ||uv|| and ||wv|| < ||uv||.

References