Grafo Ordenado (Ordered Theta Graph, OG)

Esta variante de los Theta Grafos consigue acotar tanto el grado máximo como el diámetro del grafo. Se debe a un trabajo de Pat Morin, Prosejint Bose y Joachim Gudmundsson.

La idea es procesar los puntos de conjunto inicial S en un cierto orden para la construcción del Theta Grafo. Los resultados que se obtienen son:

1. Si los puntos se ordenan aleatoriamente, el diámetro del grafo resulta acotado con una cierta probabilidad.

2. Eligiendo adecuadamente el orden de procesado de los puntos se consigue que el Theta Grafo construido tenga grado máximo acotado.