Planaridade

Questões-guia:

1. Como é o problema de gás-água-eletricidade?  Ele tem solução?  E se fossem 5 vizinhos querendo se conectar todos com todos?
2. O que é uma curva?  E uma curva poligonal?  O que é um desenho?  O que é um cruzamento num desenho?
3. Qual a diferença entre um grafo plano e um grafo planar?  O que é uma curva fechada?  E uma curva simples?
4. O que é um conjunto aberto?  E uma região?  O que são as faces de um grafo plano?  O que é a façe externa de um grafo plano?  Só há uma face externa num grafo plano?
5. Como se constrói o dual G* de um grafo plano G?  Dê exemplos.
6. O que é o comprimento de uma face?  A que corresponde no dual?  O que é um grafo periplanar (outerplanar)?
7. O que diz a Fórmula de Euler para grafos planos conexos?  Como se pode generalizá-la para grafos planos desconexos?
8. Um grafo simples pode ter um número quadrático de arestas, em relação ao número de vértices.  Isto pode acontecer com grafos planares simples?  Por quê?
9. O que é uma triangulação?  Quais são todos os grafos planares simples, regulares e cujo dual também é regular?  Desenhe-os no plano.  Quais deles são triangulações?

Exercícios:

1. Ex. 6.1.2 do West.
2. Ex. 6.1.14 do West.
3. Ex. 6.2.4 do West.