MO405 - Atas das Aulas

Ata de Aula: 21/10/2002
 Redator: Raimundo Claudio da Silva Vasconcelos

Tópicos mais importantes da seção 6.2 - Caracterização de grafos planares

6.2.1. Proposição. Se um grafo G tem um subgrafo que é uma subdivisão do K₅ ou K_3,3, então G não é planar.

6.2.2. Teorema. (Kuratowski [1930]) Um grafo é planar se, e somente se, ele não contém uma subdivisão do K₅ ou K_3,3.

Existem algoritmos complicados em tempo linear para verificar se um grafo possui subdivisão do K₅ ou K_3,3, ou seja, verificar se ele é planar. O livro apresenta um algoritmo (6.2.17) que possui complexidade n².