Grafos Planares
Grafos Planares, são grafos que não possui nenhuma intersecção entre
suas arestas. Considerando cada nó como um vértice, podemos transformar uma
rede em um grafo.
Os grafos de vizinhos relativos (RNG) e os grafos de Gabriel (GG) são
dois tipos de grafos planares.
Os grafos de vizinhos relativos são grafos planares que respeitam a
seguinte condição:
_
Para todo z≠ x,y: dist(x,y)≤max[dist(x,z),dist(y,z)]
Ou seja, para existir um vértice entre dois nós x e y, a distância entre
eles deve ser menor ou igual à distância entre eles e qualquer outro nó z do
grafo.
Grafo de vizinhos relativos(RNG) extraído de [7]
Os grafos de Gabriel são um caso particular dos grafos de vizinhos
relativos, eles obedecem a seguinte equação:
Para todo z≠ x,y: dist²(x,y)≤ [dist²(x,z)+dist²(y,z)]
Ou seja, para existir um vértice entre os nós x e y, não pode haver
nenhum outro nó dentro do circulo cujo diâmetro é a distancia entre x e y.
Grafo de Gabriel (GG) extraído de [7]
Qualquer abordagem que reduza o grafo da rede para um GRN
ou um GG, não deve, sob hipótese alguma, desconectar o grafo, isso
particionaria a rede.
