Grafo planar

Kazimierz Kuratowski proporcionó una caracterización de los grafos planares en términos de grafos prohibidos , ahora conocida como el teorema de Kuratowski :

Un grafo finito es planar si y solo si no contiene un subgrafo que sea una subdivisión del grafo completo K ₅ o del grafo bipartito completo K _3,3 ( grafo de utilidad ).

Una subdivisión de un grafo resulta de insertar vértices en aristas (por ejemplo, cambiar una arista • —— • a • — • — • ) cero o más veces.

En lugar de considerar subdivisiones, el teorema de Wagner trata con menores :

Un grafo finito es planar si y solo si no tiene K ₅ o K _3,3 como menor .

Un subgrafo menor se obtiene al tomar un subgrafo y contraer repetidamente una arista hasta convertirla en un vértice, de modo que cada vecino de los vértices extremos originales se convierte en vecino del nuevo vértice.

Klaus Wagner preguntó, de forma más general, si alguna clase de grafos cerrada bajo la propiedad de menores está determinada por un conjunto finito de " menores prohibidos ". Este es ahora el teorema de Robertson-Seymour , demostrado en una larga serie de artículos. En el lenguaje de este teorema, K₅ y K₃ _{, ₃} son los menores prohibidos para la clase de grafos planares finitos.

En la práctica, es difícil usar el criterio de Kuratowski para decidir rápidamente si un grafo dado es planar. Sin embargo, existen algoritmos rápidos para este problema: para un grafo con n vértices, es posible determinar en tiempo O ( n ) (tiempo lineal) si el grafo puede ser planar o no (ver prueba de planaridad ).

Para un grafo simple, conectado y planar con v vértices, e aristas y f caras, se cumplen las siguientes condiciones simples para v ≥ 3 :

• Teorema 1. e ≤ 3 v − 6 ;
• Teorema 2. Si no hay ciclos de longitud 3, entonces e ≤ 2 v − 4 .
• Teorema 3. f ≤ 2 v − 4 .

En este sentido, los grafos planares son grafos dispersos , ya que solo tienen O ( v ) aristas, asintóticamente menores que el máximo O ( v² ) . El grafo K₃ ^, _₃ , por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por lo tanto, según el Teorema 2, no puede ser planar. Estos teoremas proporcionan condiciones necesarias para la planaridad que no son suficientes y, por lo tanto, solo pueden usarse para demostrar que un grafo no es planar, no que lo es. Si fallan tanto el Teorema 1 como el 2, se pueden usar otros métodos.

• El criterio de planaridad de Whitney proporciona una caracterización basada en la existencia de un dual algebraico;
• El criterio de planaridad de Mac Lane proporciona una caracterización algebraica de los grafos planares finitos, a través de sus espacios de ciclos ;
• El criterio de planaridad de Fraysseix-Rosenstiehl proporciona una caracterización basada en la existencia de una bipartición de las aristas del cotree de un árbol de búsqueda en profundidad . Es fundamental para el algoritmo de prueba de planaridad izquierda-derecha ;
• El teorema de Schnyder proporciona una caracterización de la planaridad en términos de dimensión de orden parcial ;
• El criterio de planaridad de Colin de Verdière proporciona una caracterización basada en la multiplicidad máxima del segundo valor propio de ciertos operadores de Schrödinger definidos por el gráfico.
• El teorema de Hanani-Tutte establece que un grafo es planar si y solo si tiene un dibujo en el que cada par independiente de aristas se cruza un número par de veces; se puede utilizar para caracterizar los grafos planares mediante un sistema de ecuaciones módulo  2.

La fórmula de Euler establece que si se dibuja un grafo planar finito y conexo en el plano sin intersecciones de aristas, y v es el número de vértices, e es el número de aristas y f es el número de caras (regiones delimitadas por aristas, incluyendo la región exterior infinitamente grande), entonces

${\displaystyle v-e+f=2.}$

Como ilustración, en el grafo mariposa dado arriba, v = 5 , e = 6 y f = 3. En general, si la propiedad se cumple para todos los grafos planares de f caras, cualquier cambio en el grafo que cree una cara adicional manteniendo el grafo planar mantendría v − e + f como invariante. Dado que la propiedad se cumple para todos los grafos con f = 2 , por inducción matemática se cumple para todos los casos. La fórmula de Euler también se puede demostrar de la siguiente manera: si el grafo no es un árbol , entonces elimine una arista que complete un ciclo . Esto reduce tanto e como f en uno, dejando v − e + f constante. Repita hasta que el grafo restante sea un árbol; los árboles tienen v = e + 1 y f = 1 , lo que produce v − e + f = 2 , es decir, la característica de Euler es 2.

En un grafo finito, conexo , simple y planar, cualquier cara (excepto posiblemente la exterior) está delimitada por al menos tres aristas y cada arista toca como máximo dos caras, por lo que 3 f ≤ 2 e ; utilizando la fórmula de Euler, se puede demostrar que estos grafos son dispersos en el sentido de que si v ≥ 3 :

${\displaystyle e\leq 3v-6.}$

La fórmula de Euler también es válida para poliedros convexos . Esto no es casualidad: todo poliedro convexo puede transformarse en un grafo plano simple y conexo mediante el diagrama de Schlegel, una proyección en perspectiva del poliedro sobre un plano con el centro de perspectiva situado cerca del centro de una de sus caras. No todos los grafos planos se corresponden de esta manera con un poliedro convexo: los árboles, por ejemplo, no. El teorema de Steinitz establece que los grafos poliédricos formados a partir de poliedros convexos son precisamente los grafos planos simples 3-conexos finitos . En términos más generales, la fórmula de Euler se aplica a cualquier poliedro cuyas caras sean polígonos simples que formen una superficie topológicamente equivalente a una esfera, independientemente de su convexidad.

Los grafos planares conexos con más de una arista cumplen la desigualdad 2e ≥ 3f , ya que cada cara tiene al menos tres incidencias cara-arista y cada arista contribuye con exactamente dos incidencias. Mediante transformaciones algebraicas de esta desigualdad con la fórmula de Euler v − e + f = 2 , se deduce que para grafos planares finitos el grado medio es estrictamente menor que 6. Los grafos con un grado medio superior no pueden ser planares.

Decimos que dos círculos dibujados en un plano se tocan (o se osculan ) cuando se intersecan en un único punto. Un grafo de tipo "moneda" es un grafo formado por un conjunto de círculos, cuyos interiores no se superponen, creando un vértice para cada círculo y una arista para cada par de círculos que se tocan. El teorema del empaquetamiento de círculos , demostrado por primera vez por Paul Koebe en 1936, establece que un grafo es planar si y solo si es un grafo de tipo moneda.

Este resultado proporciona una demostración sencilla del teorema de Fáry , que establece que todo grafo planar simple puede incrustarse en el plano de tal manera que sus aristas sean segmentos de línea recta que no se cruzan entre sí. Si se coloca cada vértice del grafo en el centro del círculo correspondiente en una representación de grafo de monedas, entonces los segmentos de línea entre los centros de los círculos que se tocan no cruzan ninguna de las otras aristas.

El coeficiente de mallado o densidad D de un grafo planar, o red, es la razón entre el número f − 1 de caras acotadas (igual que el rango del circuito del grafo, según el criterio de planaridad de Mac Lane ) y sus valores máximos posibles 2 v − 5 para un grafo con v vértices:

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

La densidad obedece a 0 ≤ D ≤ 1 , donde D = 0 para un grafo planar completamente disperso (un árbol) y D = 1 para un grafo planar completamente denso (máximo). ^{[ 3 ]}

Dado un incrustamiento G de un grafo conexo (no necesariamente simple) en el plano sin intersecciones de aristas, construimos el grafo dual G* de la siguiente manera: elegimos un vértice en cada cara de G (incluida la cara exterior) y para cada arista e en G introducimos una nueva arista en G* que conecta los dos vértices en G* correspondientes a las dos caras en G que se encuentran en e . Además, esta arista se dibuja de manera que cruce e exactamente una vez y que ninguna otra arista de G o G* se interseque. Entonces G* es nuevamente el incrustamiento de un grafo planar (no necesariamente simple); tiene tantas aristas como G , tantos vértices como caras tiene G y tantas caras como vértices tiene G. El término "dual" se justifica por el hecho de que G ** = G ; aquí la igualdad es la equivalencia de incrustaciones en la esfera . Si G es el grafo planar correspondiente a un poliedro convexo, entonces G* es el grafo planar correspondiente al poliedro dual.

Los grafos duales son útiles porque muchas propiedades del grafo dual están relacionadas de forma sencilla con las propiedades del grafo original, lo que permite demostrar resultados sobre grafos examinando sus grafos duales.

Si bien el dual construido para una incrustación particular es único (salvo isomorfismo ), los grafos pueden tener duales diferentes (es decir, no isomorfos), obtenidos a partir de incrustaciones diferentes (es decir, no homeomorfas ).

Un grafo simple se denomina planar maximal si es planar, pero añadirle cualquier arista (en el conjunto de vértices dado) destruiría esa propiedad. Todas las caras (incluida la exterior) quedan entonces delimitadas por tres aristas, lo que explica el término alternativo triangulación plana (que técnicamente significa un dibujo plano del grafo). También se han utilizado los nombres alternativos «grafo triangular» ^{[ 4 ]} o «grafo triangulado» ^{[ 5 ]} , pero son ambiguos, ya que suelen referirse al grafo de líneas de un grafo completo y a los grafos cordales, respectivamente. Todo grafo planar maximal con más de 3 vértices es al menos 3-conexo. ^{[ 6 ]}

Si un grafo planar maximal tiene v vértices con v > 2 , entonces tiene precisamente 3v − 6 aristas y 2v − 4 caras .

Las redes apolíneas son los grafos planares máximos formados al dividir repetidamente las caras triangulares en tríos de triángulos más pequeños. De forma equivalente, son los 3-árboles planares .

Los grafos estrangulados son aquellos en los que cada ciclo periférico es un triángulo. En un grafo planar maximal (o, más generalmente, en un grafo poliédrico), los ciclos periféricos son las caras, por lo que los grafos planares maximales son estrangulados. Los grafos estrangulados también incluyen los grafos cordales y son precisamente los grafos que se pueden formar mediante sumas de cliques (sin eliminar aristas) de grafos completos y grafos planares maximales. ^{[ 7 ]}

Los grafos outerplanares son grafos con una incrustación en el plano tal que todos los vértices pertenecen a la cara no acotada de la incrustación. Todo grafo outerplanar es planar, pero lo contrario no es cierto: K₄ es planar pero no outerplanar. Un teorema similar al de Kuratowski establece que un grafo finito es outerplanar si y solo si no contiene una subdivisión de K₄ o de _{K₂ ,} ₃ _. Lo anterior es un corolario directo del hecho de que un grafo G es outerplanar si el grafo formado a partir de G añadiendo un nuevo vértice, con aristas que lo conectan a todos los demás vértices, es un grafo planar. ^{[ 8 ]}

Una incrustación 1-externa de un grafo es lo mismo que una incrustación externa. Para k > 1 , una incrustación planar es k -externa si al eliminar los vértices de la cara externa se obtiene una incrustación ( k − 1) -externa. Un grafo es k -externa si tiene una incrustación k -externa.

Un grafo de Halin es un grafo formado a partir de un árbol plano no dirigido (sin nodos de grado dos) mediante la conexión de sus hojas en un ciclo, en el orden dado por la incrustación plana del árbol. De forma equivalente, es un grafo poliédrico en el que una cara es adyacente a todas las demás. Todo grafo de Halin es planar. Al igual que los grafos exteriores planares, los grafos de Halin tienen un ancho de árbol bajo , lo que facilita la resolución de muchos problemas algorítmicos en ellos en comparación con los grafos planares no restringidos. ^{[ 9 ]}

Un grafo planar ascendente es un grafo dirigido acíclico que puede representarse en el plano con sus aristas como curvas que no se cruzan y que están orientadas consistentemente hacia arriba. No todos los grafos planares dirigidos acíclicos son planares ascendentes, y determinar si un grafo dado es planar ascendente es un problema NP-completo .

Se dice que un grafo planar es convexo si todas sus caras (incluida la cara exterior) son polígonos convexos . No todos los grafos planares tienen una incrustación convexa (por ejemplo, el grafo bipartito completo K _2,4 ). Una condición suficiente para que un grafo pueda dibujarse de forma convexa es que sea una subdivisión de un grafo planar con 3 vértices conexos . El teorema del resorte de Tutte incluso afirma que, para grafos planares simples con 3 vértices conexos, la posición de los vértices internos puede elegirse como el promedio de sus vecinos.

Los grafos planares representables por palabras incluyen grafos planares sin triángulos y, más generalmente, grafos planares 3-coloreables, ^{[ 10 ]} así como ciertas subdivisiones de caras de grafos de cuadrícula triangulares, ^{[ 11 ]} y ciertas triangulaciones de grafos cilíndricos cubiertos por cuadrícula. ^{[ 12 ]}

La asintótica para el número de grafos planares (etiquetados) en${\displaystyle n}$vértices es${\displaystyle g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$, dónde${\displaystyle \gamma \approx 27.22687}$y${\displaystyle g\approx 0,43\times 10^{-5}}$. ^{[ 13 ]}

Casi todos los grafos planares tienen un número exponencial de automorfismos. ^{[ 14 ]}

El número de grafos planares no etiquetados (no isomorfos) en${\displaystyle n}$vértices está entre${\displaystyle 27.2^{n}}$y${\displaystyle 30.06^{n}}$. ^{[ 15 ]}

El teorema de los cuatro colores establece que todo grafo planar es 4- coloreable (es decir, 4-partito).

El teorema de Fáry establece que todo grafo planar simple admite una representación como un grafo planar de líneas rectas . Un conjunto de puntos universal es un conjunto de puntos tal que todo grafo planar con n vértices tiene una incrustación de este tipo con todos los vértices en el conjunto de puntos; existen conjuntos de puntos universales de tamaño cuadrático, formados al tomar un subconjunto rectangular de la red entera . Todo grafo exteriorplanar simple admite una incrustación en el plano tal que todos los vértices se encuentran en un círculo fijo y todas las aristas son segmentos de línea recta que se encuentran dentro del disco y no se intersecan, por lo que los polígonos regulares de n vértices son universales para los grafos exterioresplanares.

La conjetura de Scheinerman (ahora un teorema) afirma que todo grafo planar puede representarse como un grafo de intersección de segmentos de línea en el plano.

El teorema del separador planar establece que todo grafo planar de n vértices puede particionarse en dos subgrafos de tamaño como máximo 2 n /3 mediante la eliminación de${\displaystyle O({\sqrt {n}})}$vértices. En consecuencia, los grafos planares también tienen ancho de árbol y ancho de rama.${\displaystyle O({\sqrt {n}})}$.

El teorema de la estructura del producto planar establece que todo grafo planar es un subgrafo del producto fuerte de un grafo con ancho de árbol como máximo 8 y un camino. ^{[ 16 ]} Este resultado se ha utilizado para demostrar que los grafos planares tienen un número de cola acotado , un número cromático no repetitivo acotado y grafos universales de tamaño casi lineal. También tiene aplicaciones en la clasificación de vértices ^{[ 17 ]} y la coloración p -centrada ^{[ 18 ]} de grafos planares.

Para dos grafos planares con v vértices, es posible determinar en tiempo O( v ) si son isomorfos o no (véase también el problema del isomorfismo de grafos ). ^{[ 19 ]}

Cualquier grafo planar en n nodos tiene como máximo 8(n-2) camarillas máximas, ^{[ 20 ]} lo que implica que la clase de grafos planares es una clase con pocas camarillas.

Según el teorema de Tutte sobre ciclos hamiltonianos , todo grafo planar con 4 vértices conectados tiene un ciclo hamiltoniano . ^{[ 21 ]}