grafos:criterionplanarity [WikiMat]

Uma das características mais notáveis de um grafo plano $G$ são seus ciclos faciais, os ciclos que delimitam uma face. Se $G$ é $2$-conexo, ele é coberto por seus ciclos faciais, então, de certo modo, eles formam um conjunto 'grande'. De fato, o conjunto de ciclos faciais é grande mesmo no sentido de que eles geram todo o espaço do ciclo: cada ciclo em $G$ é facilmente visto como a soma dos ciclos faciais (veja abaixo). Por outro lado, os ciclos faciais cobrem apenas $G$ 'finamente', já que cada aresta está em no máximo dois deles. Nosso primeiro objetivo é mostrar que a existência de uma família de ciclos tão grande, mas pouco difundida, não é apenas uma característica notável da planaridade, mas está em seu cerne: ela a caracteriza.

Seja $G=(V,E)$ um grafo qualquer. Chamamos um subconjunto $\mathcal{F}$ de seu espaço de arestas $\varepsilon (G)$ esparso se cada aresta de $G$ estiver em no máximo dois conjuntos de $\mathcal{F}$. Por exemplo, o espaço de corte $\mathcal{B}(G)$ tem uma base esparsa: de acordo com a Proposição ele é gerado pelos cortes $E(v)$ formado por todas as arestas em um dado vértice $v$, e uma aresta $xy \in G$ está em $E(v)$ apenas para $v=x$ e para $v=y$.

Teorema (MacLane)

Um grafo é planar se, e somente se, seu espaço de ciclo tem uma base esparsa.

Demonstração:

Sendo a afirmação trivial para grafos de ordem no máximo $2$, consideramos um grafo $G$ de ordem no mínimo $3$. Se $\kappa (G) \leq 1$, então $G$ é a união de dois subgrafos induzidos próprios $G_1,G_2$ com $|G_1 \cap G_2| \leq 1$. Então $\mathcal{C}(G)$ é a soma direta de $\mathcal{C}(G_1)$ e $\mathcal{C}(G_2)$ e, portanto, tem uma base esparsa se, e somente se, $\mathcal{C}(G_1)$ e $\mathcal{C}(G_2)$ o fazem. Além disso, $G$ é planar se, e somente se, ambos $G_1$ e $G_2$ são: isso decorre imediatamente do Teorema de Kuratowski, mas também de considerações geométricas fáceis. A firmação para $G$ segue indutivamente daquelas para $G_1$ e $G_2$. Para o restante da prova, assumimos agora que $G4 é $2$-conexo.

Primeiro assumimos que $G$ é planar e escolhemos um desenho. Pela Proposição, os limites de face de $G$ são ciclos, portanto são elementos de $\mathcal{C}(G)$. Mostraremos que os limites de face geram todos os ciclos em $G$; então $\mathcal{C}(G)$ tem uma base esparsa pelo Lema. Seja $C \subseteq G$ qualquer ciclo, e seja $f$ sua face interna. Pelo Lema, toda aresta $e$ com $\dot e \subseteq f$ está exatamente em dois limites de face $G[f']$ com $f' \subseteq f$, e toda aresta de $C$ está exatamente em um desses limites de face. Portanto, a soma em $\mathcal{C}(G)$ de todos esses limites de face é exatamente $C$.

Reciprocamente, seja $\{C_1, \dots, C_{k}\}$ uma base esparsa de $\mathcal{C}(G)$. Então, para toda aresta $e \in G$, também $\mathcal{C}(G-e)$ tem uma base esparsa. De fato, se $e$ está em apenas um dos conjuntos $C_{i}$, digamos em $C_1$, então $\{C_2, \dots, C_{k}\}$ é uma base esparsa de $\mathcal{C}(G-e)$; se $e$ está em dois de $C_{i}$, digamos em $C_1$ e $C_2$, então $\{C_1+C_2,C_3, \dots\ C_{k}\}$ é tal base. Observe que as duas bases são de fato subconjuntos de $\mathcal{C}(G-e)$ pela Proposição. Assim, todo subgrafo de $G$ tem um espaço de ciclo com uma base esparsa. Para nossa prova de que $G$ é planar, basta mostrar que os espaços de ciclo de $K^5$ e $K_{3,3}$ (e, portanto, aqueles de suas subdivisões) não têm uma base esparsa: então $G$ não pode conter um $TK^5$ ou $TK_{3,3}$ e, portanto, é planar por Teorema de Kuratowski.

Vamos considerar $K^5$ primeiro. Pelo Teorema, $dim \mathcal{C}(K^5) = 6$; seja $\mathcal{B} = \{C_1, \dots,C_6\}$ uma base esparsa,e coloque $C_0 := C_1 + \dots C_6$. Como $\mathcal{B}$ é linearmente independente , nenhum dos conjuntos $C_0, \dots, C_6$ é vazio , então cada um deles contém pelo menos três arestas (conforme, Proposição). Além disso, como toda aresta de $C_0$ está em apenas uma de $C_1, \dots, C_6$, o conjunto $\{C_1,\dots, C_6\}$ ainda é esparso. Mas isso implica que $K^5$ deve ter mais arestas do que tem, ou seja, obtemos a contradição de

$$ 21= 7*3 \leq |C_0|+ \dots + |C_6| \leq 2||K^5|| =20 $$

Para $K_{3,3}$, o Teorema dá $dim \mathcal{C}(K_{3,3}) = 4$; seja $\mathcal{B} = \{C_1, \dots, C_4\}$ uma base esparsa e coloque $C_0 := C_1 + \dots + C_4$. Como $K_{3,3}$ tem circunferência $4$, cada $C_{i}$ contém pelo menos quatro arestas. Obtemos então a contradição de

$$20 = 5*4 \leq |C_0|+ \dots + |C_4| \leq 2||K_{3,3}|| = 18$$

É uma das belezas ocultas da teoria da planaridade que dois resultados tão abstratos e aparentemente não intuitivos sobre a geração de conjuntos em espaços de ciclo como o Teorema de MacLane, logo acima, e o Teorema de Tutte conspiram para produzir um critério de planaridade muito tangível para grafos $3$-conexos:

Teorema (Kelmans)

Um grafo $3$-conexo é planar se, e somente se, todas as arestas estão no máximo (equivalentemente: exatamente) em dois ciclos induzidos não separados.

Demonstração:

$(\Rightarrow)$ Esta afirmação segue da Proposição e do Lema (e da Proposição para a versão 'exatamente dois').

$(\Leftarrow)$ Já esta implicação segue do Teorema de Tutte e do Teorema de MacLane.

Vamos concluir com outra caracterização de planaridade, uma com um sabor muito diferente. Uma extensão linear de uma ordenação parcial $\leq$ de um conjunto $P$ é uma ordenação total $\leq '$ em $P$ que inclui $\leq$ como um subconjunto de $P^2$. Assim, para qualquer $p \leq q$ em $P$ ainda temos $p \leq 'q$, e para $p,q \in P$ imcomparáveis temos $p <'q$ ou $p >'q$, além disso. A dimensão do conjunto parcialmente ordenado $(P,\leq)$ é o menor número de extensões lineares de $\leq$ em $P$ cuja interseção é exatamente $\leq$ : para qualquer $p,q \in P$ incomparáveis deve haver uma extensão linear $\leq '$ com $p <'q$ e outra extensão linear $\leq ''$ com $p >''q$ nesta coleção.

A cada grafo $G=(V,E)$ pode-se associar sua pose de incidência, o conjunto parcialmente ordenado $(V \cup E, \leq)$ em que $v < e$ se, e somente se, $v$ é um vértice e $e$ é uma aresta em $v$. (Assim, como uma relação, $<$ é o mesmo que $\in$.)