Grafo planar

TRABALHO DE TEORIA DOS GRAFOS

Alunos: Curso:
Prof.:

ANO 2013 1) Descrição detalhada
O grafo planar é aquele que admite uma representação gráfica na qual as arestas só se encontrem (possivelmente) nos vértices aos quais são incidentes, ou seja, deve admitir uma representação, também chamada de forma topológica ou grafo plano, em que suas arestas não se intersectem.
Para entender melhor, imagine pegar uma forma sólida e esticar uma das faces dela de modo que as arestas fiquem sobre um plano, assim todas as outras faces e arestas do sólido formarão um desenho no interior dessa primeira face, desenhando um grafo.
Se as arestas não se cruzarem, esse grafo é planar, por exemplo, temos o dado, que é formato sólido de um cubo.
A representação gráfico 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.
As formas para verificar se o grafo é planar são baseadas do Teorema de Kuratowski e na Fórmula de Euler.

2) Exemplos de grafos planares

Observe que no primeiro grafo, a imagem mostra que as arestas estão se cruzando, mas o grafo não deixa de ser planar, pois isso ocorre não por obrigação, e sim apenas para mostrar que o mesmo K4 pode ser desenhado de outras formas as quais não apareçam com arestas cruzadas, como mostrado nos outros 2 desenhos, e por tanto essa representação de K4 é planar.

3) Aplicações de grafos planares
Esses grafos são utilizados para desenvolvimento de circuito impresso, e em mapas para pintura deles, como mapas de estados e malhas de transporte como mêtros.

4) Referência bibliográfica
FONTES, F. C. Fábio. Aula 10 grafos planares.pst. UFERSA, Abril de 2009
Autor não identificado. Conceito Básicos da Teoria dos Grafos. Publicado em