Grafo Sink Spanner (Sink Spanner Graph, SSG)

Esta variante de los Theta Grafos (dirigidos) consigue rebajar el grado de entrada de los vértices en el grafo final.

Sea S el conjunto de n puntos del plano; sea q un punto de S; y sea t > 1 un número real. Un grafo dirigido que tenga los puntos de S como sus vértices será q-sink t-spanner para S si para cada punto p de S existe un camino t-spanner directo desde p a q en este grafo.

Los objetivos concretos que se persiguen en la construcción de un q-sink t-spanner son (i) que cada vértice tiene un grado de entrada limitado por una constante entera que depende sólo de t; (ii) el grado de salida de q es 0; y (iii) cada vértice restante tiene un grado de salida igual a 1.

El funcionamiento de los sink spanners es el siguiente. Se estudia cada nodo del theta grafo. Se analiza cada nodo que presente un grado de entrada superior a uno. Para cada cono de dicho nodo v, se aplica un algoritmo, consistente en calcular un theta grafo independiente para todos los nodos que pertenezcan al cono en cuestión, llamado k. De este modo, en lugar de que varios nodos tuvieran una arista incidente en nuestro nodo v, tan sólo tendrá una arista de entrada, la de la proyección más cercana. El resto de aristas que antes eran incidentes en v, se recalculan mediante la construcción de un theta grafo formado sólo por los puntos pertenecientes al cono k. Si repetimos la misma operación para todos los nodos del plano, y para todos los conos de dichos nodos, recalcularemos el theta grafo hasta alcanzar un spanner de grado máximo acotado.

El resultado que se puede demostrar es el siguiente:

Teorema: En el grafo q (S, q, k), el grado de entrada de cada vértice es menor o igual a la suma k + 1, el grado de salida es 0, mientras el grado del resto de vértices es 1. Por tanto, el grafo q (S, q, k) se construye en un tiempo con la complejidad O (k + n log n log k).