Grafo de Yao Yao (Yao Yao Structure, YY)
Este grafo se construye a partir del Grafo de Yao eliminando alguna de sus aristas.
Dado un conjunto de puntos S del plano, se construye inicialmente su grafo de Yao, Y(S). Y aplicando el mismo proceso en cada uno de sus nodos v, se elige la arista más corta de cada uno de los conos de v borrando las demás aristas incidentes en v.
A pesar de esta eliminación de aristas el grafo de YaoYao conserva buenas propiedades:
Propiedad 1: El Grafo YYk(V) es fuertemente conexo si y sólo si UDG(V) (Grafo de Disco Unidad) es conexo y k > 6.
Propiedad 2: El factor de dilación del grafo dirigido YYk(V) está acotado por una constante.