Grafo planar

Keywords: Grafo planar, Grafo, Teoria dos grafos

Na teoria dos grafos, um grafo planar é um grafo que pode ser representado no plano de tal forma que suas arestas não se cruzem. Por exemplo, os dois grafos seguintes são planares:

Imagem:6n-graf.png         Imagem:Graph_k4.jpg

(o segundo pode ser redesenhado sem intersecção das arestas, movendo um dos vértices interiores para o exterior),

ao passo que os dois grafos abaixo não são planares:

Imagem:GraphK5.png        Imagem:GraphK33.png

Não é possível redesenhar estes grafos sem que as arestas se cruzem.

Keywords: Grafo planar, Grafo, Teoria dos grafos