planaridade

Planaridade é a propriedade de ser plano ou de poder ser representado no plano sem interseções indesejadas entre elementos. No âmbito da teoria dos grafos, um grafo é planar se pode ser desenhado num plano de modo que as arestas só se encontrem nos vértices aos quais pertencem. Em desenhos, as arestas podem ser curvas; também se costuma distinguir entre planaridade topológica (em que se aceita curvas) e planaridade geométrica (em que as arestas são frequentemente consideradas como segmentos de reta).

Critérios e teoremas fundamentais: o teorema de Kuratowski estabelece que um grafo simples é planar se e somente se não contiver um subgrafo que seja casa (homeomorfo) de K5 ou de K3,3. Outra maneira de caracterizar planaridade é pela minimização de minors, conforme o teorema de Wagner. Para grafos conectados e planários, a fórmula de Euler vale: V - E + F = 2, onde V é o número de vértices, E o de arestas e F o de faces. Consequência prática: em grafos simples com V ≥ 3, E ≤ 3V - 6; se não houver triângulos, E ≤ 2V - 4. Alguns grafos não planars clássicos são K5 (grafo completo em cinco vértices) e K3,3 (grafo emparelhado com três pares de vértices).

Disposição prática e algoritmos: existem métodos de teste de planarity com complexidade linear no tamanho da entrada, capazes de decidir a planaridade e, se possível, produzir uma embedding planar; exemplos incluem os algoritmos de Hopcroft-Tarjan e melhorias subsequentes.

Aplicações: a noção de planaridade é central em desenho de circuitos, redes de transporte e cartografia, onde evita-se cruzamento de arestas. Em contextos além do plano, usam-se termos como planaridade em superfícies diferentes do plano, destacando-se que a propriedade específica pode depender da superfície considerada.

---