Grafo planar
Origem: Wikipédia, a enciclopédia livre.
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:
Segundo o Teorema de Kuratowski, um grafo planar não apresenta nem o K5 nem o grafo bipartido K3,3 como subgrafos. A prova de que o K3,3 não é planar pode ser feita de duas formas: por indução e por construção, enquanto a do K5 é feita apenas por construção.
Não é possível redesenhar estes grafos sem que suas arestas se cruzem.
