Os números de capítulos, seções, teoremas e exercícios se referem ao livro de Diestel, 2-a edição.

4. Planaridade

Quais grafos podem ser desenhados no plano sem que as arestas se cruzem? A teoria da planaridade gira em torno dos ciclos de grafos (e acaba envolvendo, inevitavelmente, os cortes minimais).

4.2 Grafos planos e suas faces

Grafo plano (= plane graph = plane map): par (V, E) onde
- V é um subconjunto finito do plano (R²)
- todo elemento de E é um arco poligonal entre dois elementos de V
- elementos diferentes de E têm diferentes conjuntos de pontas
- o interior de um elemento de E não contém elementos de V nem pontos que pertençam a outro elemento de E.
Os elementos de V são chamados vértices e os de E são chamados arestas.
Um arco (ou arco poligonal) é a união de um número finito de segmentos de reta no plano que seja homeomorfa ao intervalo fechado [0,1] da reta. As imagens de 0 e 1 sob esse homeomorfismo são as pontas (= extremos = endvertices) do arco.
Todo grafo plano (V, E) corresponde obvia e naturalmente a um grafo combinatório.
Um grafo plano — ou melhor, o conjunto de pontos de um grafo plano — é um subconjunto fechado (no sentido topológico) e limitado do plano R².
Uma face de um grafo plano G é qualquer região do conjunto (topologicamente) aberto R² − G. Se H é subgrafo de G então toda face de H é parte de uma face de G.
A fronteira (topológica) de uma face corresponde naturalmente a um subgrafo do grafo.
Proposição 4.2.5: Num grafo plano 2-conexo, a fronteira de cada face é um ciclo.
Proposição 4.2.10: Num grafo plano 3-conexo, a fronteira de cada face é um ciclo induzido não separador e todo ciclo induzido não separador é fronteira de alguma face.
Aqui, um ciclo C é separador se existem vértices x e y fora de C tais que qualquer caminho de x a y passa por C.
Teorema 4.2.7 (fómula de Euler): Todo grafo plano conexo G satisfaz a identidade |G| − ‖G‖ + ‖‖G‖‖ = 2, onde ‖‖G‖‖ é o número da faces de G.
Corolário 4.2.8: Se G é plano e |G| ≥ 3 então ‖G‖ ≤ 3|G| − 6.
Corolário: Não existe grafo plano isomorfo a K⁵.

Exercícios:
1. [4.5] Mostre que todo grafo plano é a união de três florestas.

4.3 Desenhos

Um desenho (= drawing) de um grafo combinatório G é um grafo plano H isomorfo a G.
Quando dois desenhos de um mesmo grafo são diferentes?
Conceitos de isomorfismo entre grafos planos (todos começam com um isomorfismo entre os grafos combinatórios correspondentes):
- isomorfismo topológico (induzido por isomorfismo do plano),
- isomorfismo combinatório que pode ser estendido a uma bijeção entre faces que preserva incidência entre faces e arestas (este é o mais natural).
Teorema 4.3.1: Para grafos planos 2-conexos, todo isomorfismo combinatório é topológico.
Dois desenhos de um grafo combinatório 2-conexo são equivalentes se forem combinatorialmente (e portanto também topologicamente) isomorfos. [Isso é tecnicamente um pouco diferente do que Diestel diz, mas acho que dá no mesmo.]
Teorema 4.3.2 (Whitney): Dois quaisquer desenhos de um grafo combinatório 3-conexo são equivalentes. [Isso é tecnicamente um pouco diferente do enunciado em Diestel.]

4.4 Grafos planares

Um grafo combinatório é planar (= planar) se é isomorfo a um grafo plano (isto é, se admite um desenho).
Teorema 4.4.6 (Kuratowski; Wagner): As seguintes afirmações são equivalentes:
1. G é planar,
2. G não inclui K⁵ nem K_3,3 como máinor e
3. G não inclui K⁵ nem K_3,3 como máinor topológico.
Corolário: G é planar se e só se G não contém uma subdivisão de K⁵ nem de K_3,3.

Exercícios:
1. [4.4] Mostre que para todo grafo planar conexo G com pelo menos um ciclo tem-se ‖G‖ ≤ (|G|−2) g / (g−2), onde g é a cintura de G.
2. Suponha que G é a união de grafos H e F e que H e F só têm dois vértices, x e y, em comum. Se G não contém uma subdivisão de K⁵ nem de K_3,3 então H + xy também não contém uma subdivisão de K⁵ nem de K_3,3.
3. Suponha que G é um grafo 3-conexo sem máinor K⁵ e sem máinor K_2,3. Suponha que G tem uma aresta e tal que G−e é 3-conexo e tem um desenho H. Tente transformar H num desenho de G. Quais as dificuldades?
  Suponha que G é um grafo 3-conexo sem máinor K⁵ e sem máinor K_2,3. Suponha que G tem um vértice v tal que G−v é 3-conexo e tem um desenho H. Tente transformar H num desenho de G. Quais as dificuldades?
4. [4.13] Mostre que qualquer máinor de um grafo planar é planar. Deduza que um grafo é planar se e só se é o máinor de uma grade. Não use o Teorema 4.4.6.
  Uma grade k×k é um grafo cujos vértices são todos os pares da forma (i, j) com i e j em {1, … , k} e cujas arestas são os pares {(i, j), (p, q)} com |i−p|+| j−q| = 1.
5. [4.14] Mostre, sem usar o Teorema 4.4.6, que existe uma coleção X de grafos tal que um grafo é planar se e só se nenhum de seus máinors topológicos está em X. Que outras propriedades de grafos (além de planaridade) podem ser caracterizadas dessa maneira?
6. [4.20] Um grafo é exoplanar (= outerplanar) se admite um desenho tal que todo vértice está na fronteira da face externa (= ilimitada). Mostre que um grafo é exoplanar se e só se não contém K⁴ nem K_2,3 como máinor.

4.5 Critérios algébricos de planaridade

Uma coleção F de subconjuntots de E(G) é simples se toda aresta de G pertence a no máximo dois membros de F.
Teorema 4.5.1 (MacLane): G é planar se e só se o espaço dos ciclos de G tem uma base simples. (Ou seja, G é planar se e só se tem um coleção simples C de ciclos tal que toda soma simétrica de ciclos também é soma simétrica de membros de C.)

Exercícios:
1. Mostre que o Teorema 4.5.1 equivale à seguinte afirmação: G é planar se e só se tem um coleção C de ciclos tal que (1) todo ciclo de G é soma mod 2 de membros de C e (2) toda aresta de G pertence a no máximo dois membros de C.
2. [4.22] Suponha que G é um grafo plano 2-conexo. Encontre uma base do espaço de ciclos formada por fronteiras de faces.
3. Refaça, de maneira elementar, a parte da prova do teorema de MacLane (Teorema 4.5.1) que mostra que K⁵ não possui uma base simples de ciclos. Isto é, refaça, sem usar explicitamente a Proposição 1.9.2, a demonstração de que (1) qualquer gerador do espaço de ciclos tem pelo menos 6 ciclos e (2) se um conjunto de apenas 6 ciclos gera o espaço de ciclos então a soma mod 2 desses ciclos não é vazia. (Sugestão: trate cada ciclo como um conjunto de arestas.)

4. Planaridade

4.2 Grafos planos e suas faces

4.3 Desenhos

4.4 Grafos planares

4.5 Critérios algébricos de planaridade

4.6 Dualidade planar