Grafo plano

Na teoría de grafos, un **grafo plano** é un grafo que se pode mergullar no plano, é dicir, pódese debuxar no plano de forma que as súas arestas se corten só nos seus extremos. 

Noutras palabras, pódese debuxar de forma que ningúnha aresta se cruce.

Todo grafo que se poida debuxar nun plano tamén se pode debuxar na esfera, e viceversa, mediante proxección estereográfica.

Os grafos planos pódense codificar mediante mapas combinatorios ou sistemas de rotación.

Os grafos planos xeneralízanse como grafos que se poden debuxar nunha superficie dun genus determinado. Nesta terminoloxía, os grafos planos teñen genus 0, xa que o plano (e a esfera) son superficies de genus 0. Consulte "mergullo de grafos" para outros temas relacionados.

## Criterios para ser plano 
### Teoremas de Kuratowski e Wagner 
thumb|200x200px|Proba sen palabras de que un grafo hipercubo non é plano usando os teoremas de Kuratowski ou Wagner e atopando os subgrafos K5 (arriba) ou K3,3 (abaixo). O matemático polaco Kazimierz Kuratowski proporcionou unha caracterización dos grafos planos en termos de grafos prohibidos, agora coñecido como teorema de Kuratowski:

: Un grafo finito é plano se e só se non contén un subgrafo que sexa unha subdivisión do grafo completo  ou do grafo bipartito completo  (grafo de utilidade).

Unha subdivisión dun grafo resulta de inserir vértices nas arestas (por exemplo, mudar unha aresta  cero ou máis veces.
miniatura| Un exemplo de grafo sen subgrafos  ou . Porén, contén unha subdivisión de  e, polo tanto, non é plana.
En lugar de considerar as subdivisións, o teorema de Wagner trata dos menores:

: Un  grafo finito é plano se e só se non ten  ou  como menor.

Un menor dun grafo resulta de tomar un subgrafo e contraer repetidamente unha aresta nun vértice, con cada veciño dos vértices finais orixinais converténdose nun veciño do novo vértice.
[miniatura|484x484px| Unha animación que mostra que o [grafo de Petersen contén un grafo menor isomorfo ao grafo  e, polo tanto, non é plano.]]
Klaus Wagner preguntou de xeito máis xeral se algunha clase de grafos pechados menores está determinada por un conxunto finito de "menores prohibidos". Este é agora o teorema de Robertson-Seymour, demostrado nunha longa serie de artigos. Na linguaxe deste teorema,  e  son os menores prohibidos para a clase de grafos planos finitos.

## Propiedades 
### Fórmula de Euler 
**A característica de Euler** indica que se se debuxa no plano un grafo plano, conexo e finito sen ningunha intersección de arestas, e  é o número de vértices,  é o número de arestas e  é o número de caras (rexións limitadas por arestas, incluída a rexión exterior infinitamente grande), entón

: v-e+f=2.

A modo de ilustración, no grafo de bolboreta mostrado na primeira figura, ,  e  (5-6+3=2). 

Nun grafo finito, conexo, *simple* e plano, calquera cara (excepto posibelmente a exterior) está limitada por polo menos tres arestas e cada aresta toca como máximo dúas caras, polo que ; usando a fórmula de Euler, pódese mostrar que estes grafos son *escasos* no sentido de que se :

: e\leq 3v-6.

[miniatura| Un [diagrama de Schlegel dun dodecaedro regular, formando un grafo plano a partir dun poliedro convexo.]]

### Grao medio 
Os grafos planos conexos con máis dunha aresta obedecen á desigualdade , porque cada cara ten polo menos tres incidencias cara-aresta e cada aresta aporta exactamente dúas incidencias. Dedúcese mediante transformacións alxébricas desta desigualdade coa fórmula de Euler  que para os grafos planos finitos o grao medio é estritamente inferior a 6. Os grafos con grao medio máis alto non poden ser planos.

### Grafos de moedas 
miniatura| Exemplo do teorema de empaquetamento circular en , o grafo completo en cinco vértices, menos unha aresta.
Dicimos que dous círculos debuxados nun plano *se bican* (ou *osculan*) sempre que coinciden nun único punto. Un "grafo de moedas" é un grafo formado por un conxunto de círculos, dos que non hai dous interiores superpostos, facendo un vértice para cada círculo e unha aresta para cada par de círculos que se bican. O teorema de empaquetamento circular, probado por primeira vez por Paul Koebe en 1936, afirma que un grafo é plano se e só se é un grafo de moedas.

### Densidade do grafo plano 
O coeficiente de retícula  ou densidade  dun grafo plano, ou rede, é a relación entre o número  de caras limitadas (o mesmo que o rango do circuíto do grafo, segundo o criterio de grafo plano de Mac Lane ) polos seus valores máximos posíbeis  para un grafo con  vértices:

: D = \frac{f-1}{2v-5}

A densidade obedece , con  para un grafo plano completamente escaso (unha árbore) e  para un grafo plano completamente denso (máximal).

### Grafo dual 
[miniatura|146x146px| Un grafo plano e o seu [Grafo dual|dual]]
Dado un mergullo  dun grafo conexo (non necesariamente simple) no plano sen interseccións de arestas, construímos o *grafo dual*  do seguinte xeito: escollemos un vértice en cada cara de  (incluída a cara exterior) e para cada aresta  en  introducimos unha nova aresta en  que une os dous vértices en  correspondentes ás dúas caras de  que se atopan en  en G. 

A maiores, esta aresta debúxase de xeito que atravese  exactamente unha vez e que non corte ningunha outra aresta de  ou . Daquela  é de novo un mergullo dun grafo plano (non necesariamente simple); ten tantas arestas como , tantos vértices como  teña caras e tantas caras como  teña vértices. 

O termo "dual" xustifícase polo feito de que ; aquí a igualdade é a equivalencia de mergullos na esfera. Se  é o grafo plano correspondente a un poliedro convexo, entón  é o grafo plano correspondente ao poliedro dual.

Aínda que o dual construído para un mergullo particular é único (ata  isomorfismo), os grafos poden ter diferentes duais (é dicir, non isomorfos), obtidos a partir de diferentes mergullos (é dicir, non homeomorfos).

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
*  Special Issue on Graph Drawing
* 
* 

### Outros artigos 
* Mapa combinatorio 
* Aplanarización
* Problema das tres casas
### Ligazóns externas 
*Edge Addition Planarity Algorithm Source Code, version 1.0  contén Edge Addition Planarity Algorithms, current version.
*Public Implementation of a Graph Algorithm Library and Editor, GPL biblioteca de algoritmos de grafos que inclúe probas de grafos planos, megullador de grafos planos e exposición de subgrafos de Kuratowski en tempo linear.
*Boost Graph Library tools for planar graphs, similar á anterior.
*3 Utilidades de Puzzle e Grafos planos
*NetLogo Planarity model,  NetLogo versión do xogo de John Tantalo