Matemáticamente, dado un grafo ${\displaystyle G=(V,E)}$ , su grafo de vecindad relativa se define como ${\displaystyle RNG(G)}$ , cumpliendo:

${\displaystyle RNG(G)=\{uv\in E:(\not \exists w\in E:uw\in E,wv\in E,||uw||<||uv||,||wv||<||uv||)\}}$ 

Supowit (1983) demostró que es posible construir eficientemente grafos de vecindad relativa en un tiempo ${\displaystyle O(nlog(n))}$ .^[2]​ Para vértices aleatorios distribuidos uniformemente en un cuadrado, el Relative Neighbor Graph se puede calcular en un tiempo ${\displaystyle O(n)}$ .^[3]​ Además, se puede computar en un tiempo lineal a partir de la triangulación de Delaunay del conjunto de puntos (vértices).^[4]​