Los grafos de proximidad son grafos geométricos, construidos sobre un conjunto S de puntos del plano, donde la relación de adyacencia se define a partir de cierta noción de proximidad. Algunos ejemplos son:
Grafo de Vecindad Relativa (RNG): Dos puntos a y b son adyacentes si la lente L, intersección de los círculos de centros a y b y radio dist (a,b), no contiene a ningún punto de S.
Grafo de Gabriel (GG): Dos puntos a y b son adyacentes si el círculo de diámetro ab, no contiene a ningún punto de S.
Triangulación de Delaunay (DT): Dos puntos a y b son adyacentes si existe algún círculo que pasa por a y por b y que no contiene en su interior a ningún otro punto de S.
Una de las propiedades interesantes en una red es que la distancia entre dos nodos medida sobre ella no difiera mucho de la distancia euclídea entre ellos, es decir que su dilación sea pequeña. Los spanners responden a este objetivo., siendo grafos que aproximan el grafo completo eucídeo sobre los puntos de la red.
Dado un grafo geométrico G = (V, A). Un t-spanner de G es un subgrafo G’ = (V, A') tal que para cada par de puntos u, v de V existe un camino P de u a v cuya longitud es, a lo más, t·|uv|.
Dilación (Stretch Factor or Dilation)
Si G = (V, A) es un grafo geométrico, diremos que la dilación de G es el número real t más pequeño para el que G’ = (V, A’) es un t-spanner de G.
El grafo de Gabriel y el de Vecindad Relativa no tienen dilación acotada, pero sí la triangulación de Delaunay.