Grafo planar

Em Teoria dos Grafos, um grafo planar e um grafo que pode ser imerso no plano de tal forma que suas arestas nao se cruzem, esta e uma idealizacao abstrata de um grafo plano, um grafo plano e um grafo planar que foi desenhado no plano sem o cruzamento de arestas.^[1]

Aparentemente o estudo da planaridade de um grafo e uma questao topologica que se baseia em resultados como o Teorema da Curva de Jordan que de forma simplificada diz que uma curva fechada simples no plano divide-o em duas partes, apesar deste ser um criterio muito importante, e natural o questionamento se ha algum resultado combinatorio que caracterize um grafo plano.

Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porem apenas o que e desenhado sem cruzamento de arestas e um grafo plano.

Uma das motivacoes mais antigas para o estudo da planaridade de um grafo e o famoso problema das tres casas. Este problema foi proposto por Henry Dudeney em 1913.^[2] E pode ser enunciado matematicamente na seguinte forma, dado um grafo K_3,3 , sabemos que este e um grafo bipartido, completo, gostariamos de saber se este grafo pode ser desenhado no plano de forma que nenhuma aresta cruze outra. E possivel tal desenho?

Segundo o Teorema de Kuratowski, um grafo planar nao pode apresentar nem o grafo completo K₅ nem o grafo bipartido K_3,3 como subgrafos. A prova de que o K_3,3 nao e planar pode ser feita de duas formas: por inducao e por construcao, enquanto a do K₅ e feita apenas por construcao.

Nao e possivel redesenhar estes grafos sem que suas arestas se cruzem.

• Representacao do K5 (um grafo completo com 5 vertices).
• Representacao do K3,3 (um grafo bipartido completo com 6 vertices).

• Teorema de Kuratowski
• Teorema das Quatro Cores

• Teoria dos grafos