Grafo planar

GRAFO PLANAR

Um grafo diz­se planar se for possível desenhá­lo de tal forma que duas arestas não se intersectem à excepção nos vértices inicial e final.

 Um exemplos clássicos de grafos planares são dados pelos grafos que representam os poliedros.
Abaixo um poliedro regular, o cubo e o grafo que o representa um grafo regular. A representação gráfica de um grafo planar na qual as arestas só se encontram uma com outra nos vértices não é única. Um grafo planar sempre a possui e ela se chama forma topológica ou grafo plano.

Veja, porém, que podemos representar K4 pelo menos de duas maneiras, a primeira admitindo cruzamento de arestas e a segunda não:

Em todo grafo planar vale a fórmula de Euler N − A + R = 2, onde N é o número de vértices, A é o número de arestas e R é o número de regiões

divididas no plano pelo grafo.

N = 13, A = 19 e R = 8. Logo 13 − 19 + 8 = 2.
Detecção de Planaridade
Em um grafo F podemos, com segurança, contrair todos os vértices de grau 2 sem afetar seu planaridade. Esse processo é chamado de
Redução Elementar.
Depois dessa operação, o grafo resultante G é:
1. uma única aresta;
2. um grafo completo com 4 vértices; ou
3. um grafo com n>= 5 e m>=7.
Se G estiver nas condições 1 ou 2 ele é planar, senão, continua­se a investigação. ● Vértices: portas lógicas.
● Arestas: fios entre as portas lógicas
● Encontrar um desenho do circuito sem cruzamento de fios.
Referencias
PATRICIO,Pedro.Grafos Planares. Grafos Planares. 2006 Disponível em: Acesso em:
02/04/2013.
FONTES, Fábio F. da Costa. Grafos Planares. Disponível em: Acesso em: 02/04/2013.
MEDEIROS,Esdras. Isomorfismos de Grafos, Grafos Planares e Árvores. Disponível em: Acesso em: 02/04/2013.
SANTOS, Haroldo Gambini. Planaridade. 2011 Disponível em: Acesso em:
02/04/2013.