Grafo plano

En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K₅ y el K_3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

Grafos de ejemplo
Plano	No plano
	K5
El grafo completo K4 es plano	K3,3

Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de género arbitrario. En esta terminología, los grafos planos tienen género 0, por ser el plano y la esfera de género 0.

Teorema de Kuratowski

El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos, conocida como el teorema de Kuratowski:​

Teorema de Kuratowski Un grafo es plano si y solo si no contiene un subgrafo isomorfo a una subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices). Kuratowski (1930)

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:

Un grafo es plano si y solo si no contiene ningún subgrafo homeomorfo a K5 o K3,3

Otros criterios para determinar si un grafo es plano

En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de n vértices y a el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:

Teorema 1 Si G es un grafo plano con n ≥ 3 vértices, entonces a ≤ 3n - 6

En otras palabras, un grafo plano de n vértices, donde n es igual o mayor a 3, tiene a lo sumo 3n-6 aristas.

Demostración del teorema 1

Supongamos el caso en el cual tenemos un grafo plano G triangular, es decir, un grafo con caras delimitadas por tres aristas, también llamados grafos planos maximales de v vértices, a aristas y c caras. Como cada cara/región tiene 3 aristas como frontera, y cada arista es borde de 2 caras, se tiene que 3c ≤ 2a. Ahora bien, por la fórmula de Euler se tiene que v − a + c = 2, multiplicando por tres resulta 3v − 3a + 3c = 6, reemplazando 3c por 2a nos queda 3v − a ≥ 6, y despejando resulta a ≤ 3v - 6. Como todo grafo plano con más de 3 vértices puede ser triangular añadiendo aristas, tenemos que a ≤ 3v-6 ∎

Teorema 2 Si n > 3 y no existen ciclos de longitud 3, entonces a ≤ 2n - 4

Demostración del teorema 2

Sea G un grafo plano libre de triángulos, es decir, sin subgrafos isomorfos a C3, de v vértices, a aristas y c caras. Las caras de este grafo deben estar limitadas por un ciclo de longitud al menos 4, por lo tanto, 2a ≥ 4c. Por la fórmula de Euler se tiene que v − a + c = 2, multiplicando por cuatro resulta 4v − 4a + 4c = 8, despejando 4c nos queda 4c = 8 - 4v + 4a. Ahora reemplazando esta expresión en la desigualdad 2a ≥ 4c nos queda 2a ≥ 8 - 4v + 4a y despejando resulta a ≤ 2v - 4 ∎

K₅ no es plano, en efecto, por el teorema 1 un grafo plano de 5 vértices puede tener como máximo 9 aristas, pero K₅ tiene 10 aristas, por lo tanto no es plano. El grafo K_3,3, por ejemplo, tiene 6 vértices, ningún ciclo de longitud 3 y 9 aristas, por el teorema 2, no puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si-entonces), y no bicondicional (si y solo si) y por tanto, solamente pueden ser usados para probar que el grafo no es plano, pero no que sea plano. Si ambos teoremas fallan, deben usarse otros métodos.

Todo grafo asociado a un poliedro es plano. En la imagen, un dodecaedro.

Fórmula de Euler

La fórmula de Euler enuncia que si un grafo conexo, planar (es dibujado sobre un plano sin intersección de aristas), y siendo v el número de vértices, a el de aristas y c la cantidad de caras (regiones conectadas por aristas, incluyendo la región externa e infinita), entonces:

Si un grafo simple plano conexo tiene v vértices, a aristas y c caras, entonces v − a + c = 2

Por ejemplo, la característica de Euler es 2. De manera más ilustrativa, en los ejemplos anteriores, en el primer grafo plano tenemos: v=6, a=7 y c=3. Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos v=4, a=6 y c=4. La fórmula de Euler se puede probar de la siguiente manera: si el grafo no es un árbol, entonces se elimina una arista que completa un ciclo. Esto disminuye el valor de a y c en uno, dejando v − a + c constante. Repítase hasta llegar a un árbol. Los árboles tienen v = a + 1 y c = 1, verificando la fórmula v - a + c = 2.

En un grafo simple, conexo y plano, cualquier región (posiblemente exceptuando la exterior) está conectada por al menos tres aristas y cada arista toca como mucho dos regiones. Usando la fórmula de Euler, se puede demostrar que estos grafos son escasos en el sentido que a ≤ 3v - 6 si v ≥ 3.

Se le dice plano maximal al grafo que es plano pero al agregarle cualquier arista dejase de serlo. Todas las regiones (incluso la externa) están limitadas por tres aristas, explicando la definición alternativa de triangular para este tipo de grafos. Si un grafo triangular tiene v vértices con v > 2, entonces tiene exactamente 3v - 6 aristas y 2v - 4 regiones.

Nótese que la fórmula de Euler también es válida para poliedros simples. No es una casualidad: cada poliedro simple se puede ver como un grafo plano y conexo usando los vértices del poliedro como vértices del grafo, y las aristas del poliedro como aristas del grafo. Las caras o regiones del grafo plano resultante corresponden a las caras del poliedro. Por ejemplo, el segundo grafo plano del ejemplo corresponde a un tetraedro. Alternativamente, no todos los grafos planos y simples corresponden a un poliedro (los árboles, por ejemplo). Un teorema de Ernst Steinitz dice que los grafos planos formados a partir de poliedros convexos son precisamente los grafos planos simples y triangulares.

Bibliografía

• Boyer, John M. & Wendy J. Myrvold (2005), «On the cutting edge: Simplified O(n) planarity by edge addition.» Archivado el 15 de julio de 2006 en Wayback Machine. Journal of Graph Algorithms and Applications, vol. 8 no. 3, pp. 241-273. En inglés.
• McKay, Brendan & Gunnar Brinkmann, Generador de grafos planos
• Wagner, K. (1937), «Über eine Eigenschaft der ebenen Komplexe.» Math. Ann. 114, pp. 570-590.

Enlaces externos

• Planarity — a game based on planar graphs running inside a browser (Flash plugin required)
• gplanarity — improved game running outside of a browser
• Edge Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator.
• Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
• 3 Utilities Puzzle and Planar Graphs

• Datos: Q547823
• Multimedia: Planar graphs / Q547823