Gráfico planar

Ejemplos de gráficos
Planar	No plano
Gráfico de mariposa	Gráfica completa K 5
Gráfica completa K 4	Gráfica de utilidad K 3,3

En teoría de grafos , un grafo plano es un grafo que se puede incrustar en el plano , es decir, se puede dibujar en el plano de tal manera que sus aristas se intersequen solo en sus puntos finales. En otras palabras, se puede dibujar de tal manera que ninguna arista se cruce entre sí. ^{[1] [2]} Un dibujo de este tipo se llama grafo plano o incrustación plana del grafo. Un grafo plano se puede definir como un grafo plano con una aplicación de cada nodo a un punto en un plano, y de cada arista a una curva plana en ese plano, de modo que los puntos extremos de cada curva son los puntos mapeados desde sus nodos finales, y todas las curvas son disjuntas excepto en sus puntos extremos.

Cualquier gráfico que pueda dibujarse en un plano puede dibujarse también en la esfera , y viceversa, mediante proyección estereográfica .

Los gráficos planos pueden codificarse mediante mapas combinatorios o sistemas de rotación .

Una clase de equivalencia de dibujos topológicamente equivalentes en la esfera, generalmente con supuestos adicionales como la ausencia de istmos , se denomina mapa plano . Aunque un grafo plano tiene una cara externa o ilimitada , ninguna de las caras de un mapa plano tiene un estado particular.

Los grafos planares se generalizan a grafos que se pueden dibujar sobre una superficie de un género determinado . En esta terminología, los grafos planares tienen género  0, ya que el plano (y la esfera) son superficies de género 0. Consulte " Incorporación de grafos " para conocer otros temas relacionados.

El matemático polaco Kazimierz Kuratowski proporcionó una caracterización de los grafos planares en términos de grafos prohibidos , ahora conocidos como teorema de Kuratowski :

Un grafo finito es planar si y sólo 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 gráfico resulta de insertar vértices en los bordes (por ejemplo, cambiar un borde • —— • a • — • — • ) cero o más veces.

En lugar de considerar subdivisiones, el teorema de Wagner se ocupa de los menores :

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

Un menor de un gráfico resulta de tomar un subgráfico y contraer repetidamente una arista en un vértice, donde cada vecino de los vértices finales originales se convierte en vecino del nuevo vértice.

Klaus Wagner se preguntó de manera más general si cualquier clase de grafos cerrada menor 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 _3,3 son los menores prohibidos para la clase de grafos planos finitos.

En la práctica, resulta difícil utilizar el criterio de Kuratowski para decidir rápidamente si un grafo dado es plano. 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 plano o no (ver comprobación de planaridad ).

Para un gráfico plano simple y conexo con v vértices y 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 , en el sentido de que tienen solo O ( v ) aristas, asintóticamente menores que el máximo O ( v ² ) . El grafo K _3,3 , por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por lo tanto, por el Teorema 2, no puede ser planar. Estos teoremas proporcionan condiciones necesarias para la planaridad que no son condiciones suficientes y, por lo tanto, solo se pueden usar 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 da 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 gráficos planares finitos, a través de sus espacios de ciclo ;
• El criterio de planaridad de Fraysseix-Rosenstiehl proporciona una caracterización basada en la existencia de una bipartición de los bordes de coárbol 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 da 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 plano si y sólo si tiene un dibujo en el que cada par de aristas independientes se cruza un número par de veces; puede utilizarse para caracterizar los grafos planos mediante un sistema de ecuaciones módulo 2.

La fórmula de Euler establece que si se dibuja un grafo finito, conexo y planar en el plano sin ninguna intersección 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, incluida la región exterior infinitamente grande), entonces

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

Como ilustración, en el gráfico de mariposa dado arriba, v = 5 , e = 6 y f = 3 . En general, si la propiedad se cumple para todos los gráficos planares de f caras, cualquier cambio en el gráfico que cree una cara adicional mientras se mantiene el gráfico plana mantendría v – e + f invariante. Dado que la propiedad se cumple para todos los gráficos 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 gráfico 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 gráfico restante sea un árbol; los árboles tienen v = e + 1 y f = 1 , produciendo v – e + f = 2 , es decir, la característica de Euler es 2.

En un grafo finito, conexo , simple y plano, cualquier cara (excepto posiblemente la exterior) está limitada 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 es válida también para los poliedros convexos . No es casualidad: todo poliedro convexo puede convertirse en un grafo plano simple y conexo mediante el diagrama de Schlegel del poliedro, una proyección en perspectiva del poliedro sobre un plano con el centro de la perspectiva elegido cerca del centro de una de las caras del poliedro. No todo grafo plano corresponde a un poliedro convexo de esta manera: los árboles no lo hacen, por ejemplo. El teorema de Steinitz dice que los grafos poliédricos formados a partir de poliedros convexos son precisamente los grafos planos simples finitos 3-conexos . De manera más general, 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 obedecen a la desigualdad 2 e ≥ 3 f , porque cada cara tiene al menos tres incidencias cara-arista y cada arista contribuye exactamente con 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 mayor no pueden ser planares.

Decimos que dos círculos dibujados en un plano se besan (o se osculan ) siempre que se intersecan exactamente en un punto. Un "grafo de moneda" es un grafo formado por un conjunto de círculos, ninguno de los cuales tiene interiores superpuestos, haciendo un vértice para cada círculo y una arista para cada par de círculos que se besan. El teorema de empaquetamiento de círculos , demostrado por primera vez por Paul Koebe en 1936, establece que un grafo es plano si y solo si es un grafo de moneda.

Este resultado proporciona una prueba sencilla del teorema de Fáry , según el cual todo grafo plano simple puede estar incrustado en el plano de tal manera que sus aristas sean segmentos de línea recta que no se crucen entre sí. Si se coloca cada vértice del grafo en el centro del círculo correspondiente en una representación gráfica de moneda, entonces los segmentos de línea entre los centros de los círculos que se besan no cruzan ninguna de las otras aristas.

El coeficiente de malla o densidad D de un grafo o red plana es la relación entre el número f – 1 de caras acotadas (el mismo que el rango del circuito del grafo, según el criterio de planaridad de Mac Lane ) por 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 , con D = 0 para un gráfico planar completamente disperso (un árbol), y D = 1 para un gráfico planar completamente denso (máximo). ^[3]

Dado un embebido 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 a e exactamente una vez y que ninguna otra arista de G o G* sea intersecada. Entonces G* es nuevamente el embebido de un grafo planar (no necesariamente simple); tiene tantas aristas como G , tantos vértices como G tiene caras y tantas caras como G tiene vértices. El término "dual" se justifica por el hecho de que G ** = G ; aquí la igualdad es la equivalencia de embebidos 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 duales son útiles porque muchas propiedades del gráfico dual están relacionadas de manera simple con las propiedades del gráfico original, lo que permite demostrar resultados sobre los gráficos examinando sus gráficos duales.

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

Un grafo simple se llama planar maximalista si es plano, pero agregar cualquier borde (en el conjunto de vértices dado) destruiría esa propiedad. Todas las caras (incluida la exterior) están entonces limitadas por tres bordes, lo que explica el término alternativo de 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 se refieren más comúnmente al grafo lineal de un grafo completo y a los grafos cordales respectivamente. Todo grafo planar maximalista en más de 3 vértices es al menos 3-conexo. ^[6]

Si un grafo plano maximalista tiene v vértices con v > 2 , entonces tiene precisamente 3 v – 6 aristas y 2 v – 4 caras.

Las redes apolíneas son los grafos planos máximos que se forman al dividir repetidamente las caras triangulares en triples de triángulos más pequeños. Equivalentemente, son los 3-árboles planos .

Los grafos estrangulados son aquellos en los que cada ciclo periférico es un triángulo. En un grafo plano maximalista (o más generalmente un grafo poliédrico) los ciclos periféricos son las caras, por lo que los grafos planos maximalistas están estrangulados. Los grafos estrangulados incluyen también los grafos cordales , y son exactamente los grafos que se pueden formar mediante sumas de clique (sin eliminar aristas) de grafos completos y grafos planos maximalistas. ^[7]

Los grafos exteplanares 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 exteplanar es plano, pero la recíproca no es cierta: K ₄ es plano pero no exteplanar. Un teorema similar al de Kuratowski establece que un grafo finito es exteplanar si y solo si no contiene una subdivisión de K ₄ o de K _2,3 . Lo anterior es un corolario directo del hecho de que un grafo G es exteplanar si el grafo formado a partir de G añadiendo un nuevo vértice, con aristas que lo conectan con todos los demás vértices, es un grafo plano. ^[8]

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

Un grafo de Halin es un grafo formado a partir de un árbol plano no dirigido (sin nodos de grado dos) conectando sus hojas en un ciclo, en el orden dado por la incrustación plana del árbol. Equivalentemente, es un grafo poliédrico en el que una cara es adyacente a todas las demás. Todo grafo de Halin es plano. Al igual que los grafos planos exteriores, los grafos de Halin tienen un ancho de árbol bajo , lo que hace que muchos problemas algorítmicos en ellos se resuelvan más fácilmente que en grafos planos sin restricciones. ^[9]

Un grafo plano ascendente es un grafo acíclico dirigido que se puede dibujar en el plano con sus bordes como curvas que no se cruzan y que están orientadas consistentemente en una dirección ascendente. No todos los grafos acíclicos dirigidos planos son planos ascendentes, y es NP-completo comprobar si un grafo dado es plano ascendente.

Se dice que un grafo plano es convexo si todas sus caras (incluida la cara exterior) son polígonos convexos . No todos los grafos planos 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 manera convexa es que sea una subdivisión de un grafo plano conexo de 3 vértices . El teorema del resorte de Tutte incluso establece que para grafos planos simples conexos de 3 vértices, la posición de los vértices internos puede elegirse como el promedio de sus vecinos.

Los gráficos planares representables mediante palabras incluyen gráficos planares sin triángulos y, de manera más general, gráficos planares de 3 colores, ^[10] así como ciertas subdivisiones de caras de gráficos de cuadrícula triangular, ^[11] y ciertas triangulaciones de gráficos cilíndricos cubiertos por cuadrícula. ^[12]

La asintótica para el número de gráficos planares (etiquetados) en los vértices es , donde y . ^[13]${\estilo de visualización n}$${\displaystyle g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$${\displaystyle \gamma \aproximadamente 27,22687}$${\displaystyle g\aproximadamente 0,43\veces 10^{-5}}$

Casi todos los gráficos planares tienen un número exponencial de automorfismos. ^[14]

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

El teorema de los cuatro colores establece que cada gráfico plano es 4- coloreable (es decir, 4-partito).

El teorema de Fáry establece que todo grafo plano simple admite una representación como grafo plano de línea recta . Un conjunto de puntos universal es un conjunto de puntos tal que todo grafo plano con n vértices tiene una incrustación tal 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 plano externo 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 grafos planos externos.

La conjetura de Scheinerman (ahora un teorema) establece que todo gráfico plano puede representarse como un gráfico de intersección de segmentos de línea en el plano.

El teorema del separador planar establece que cada grafo planar de n vértices se puede dividir en dos subgrafos de tamaño máximo 2 n /3 mediante la eliminación de O( √ n ) vértices. En consecuencia, los grafos planares también tienen un ancho de árbol y de rama O( √ n ).

El teorema de la estructura del producto planar establece que cada grafo planar es un subgrafo del producto gráfico fuerte de un grafo con un ancho de árbol de 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 para la clasificación de vértices ^[17] y la coloración centrada en p ^[18] de grafos planares.

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

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

Un gráfico de vértice es un gráfico que puede volverse plano mediante la eliminación de un vértice, y un gráfico de k -vértices es un gráfico que puede volverse plano mediante la eliminación de como máximo k vértices.

Un gráfico 1-planar es un gráfico que puede dibujarse en el plano con como máximo un cruce simple por arista, y un gráfico k -planar es un gráfico que puede dibujarse con como máximo k cruces simples por arista.

Un grafo de mapa es un grafo formado a partir de un conjunto finito de regiones interiores disjuntas, simplemente conexas, en el plano, mediante la conexión de dos regiones cuando comparten al menos un punto límite. Cuando como máximo tres regiones se encuentran en un punto, el resultado es un grafo plano, pero cuando cuatro o más regiones se encuentran en un punto, el resultado puede ser no plano (por ejemplo, si se piensa en un círculo dividido en sectores, siendo los sectores las regiones, entonces el grafo de mapa correspondiente es el grafo completo, ya que todos los sectores tienen un punto límite común: el punto central).

Un grafo toroidal es un grafo que puede ser incrustado sin cruces en el toro . De manera más general, el género de un grafo es el género mínimo de una superficie bidimensional en la que el grafo puede ser incrustado; los grafos planares tienen género cero y los grafos toroidales no planares tienen género uno. Cada grafo puede ser incrustado sin cruces en alguna superficie bidimensional cerrada (orientable, conectada) (esfera con asas) y por lo tanto el género de un grafo está bien definido. Obviamente, si el grafo puede ser incrustado sin cruces en una superficie (orientable, conectada, cerrada) con género g, puede ser incrustado sin cruces en todas las superficies (orientables, conectadas, cerradas) con género mayor o igual. También hay otros conceptos en la teoría de grafos que se llaman "género X" con "X" algún calificador; en general, estos difieren del concepto definido anteriormente de "género" sin ningún calificador. Especialmente el género no orientable de un grafo (usando superficies no orientables en su definición) es diferente para un grafo general del género de ese grafo (usando superficies orientables en su definición).

Cualquier gráfico puede ser incrustado en un espacio tridimensional sin cruces. De hecho, cualquier gráfico puede ser dibujado sin cruces en una configuración de dos planos, donde dos planos se colocan uno sobre el otro y se permite que los bordes "salten" y "bajen" de un plano al otro en cualquier lugar (no solo en los vértices del gráfico) para que los bordes puedan evitar intersecciones con otros bordes. Esto puede interpretarse como que es posible hacer cualquier red de conductores eléctricos con una placa de circuito de dos lados donde se puede hacer la conexión eléctrica entre los lados de la placa (como es posible con las placas de circuito típicas de la vida real, con las conexiones eléctricas en el lado superior de la placa logradas a través de trozos de cable y en el lado inferior por pistas de cobre construidas sobre la propia placa y la conexión eléctrica entre los lados de la placa lograda a través de agujeros, pasando los cables a través de los agujeros y soldándolos a las pistas); también se puede interpretar esto como que para construir cualquier red de carreteras, solo se necesitan puentes o solo túneles, no ambos (2 niveles son suficientes, 3 no son necesarios). Además, en tres dimensiones la cuestión de dibujar el grafo sin cruces es trivial. Sin embargo, un análogo tridimensional de los grafos planares lo proporcionan los grafos integrables sin enlaces , grafos que se pueden integrar en el espacio tridimensional de tal manera que no haya dos ciclos topológicamente vinculados entre sí. En analogía con las caracterizaciones de Kuratowski y Wagner de los grafos planares como los grafos que no contienen K ₅ o K _3,3 como menor, los grafos integrables sin enlaces pueden caracterizarse como los grafos que no contienen como menor ninguno de los siete grafos de la familia Petersen . En analogía con las caracterizaciones de los grafos planos y exteriores como los grafos con un grafo de Colin de Verdière invariante como máximo en dos o tres, los grafos integrables sin enlaces son los grafos que tienen un invariante de Colin de Verdière como máximo en cuatro.

• Mapa combinatorio un objeto combinatorio que puede codificar gráficos planos
• Planarización , un gráfico plano formado a partir de un dibujo con cruces reemplazando cada punto de cruce por un nuevo vértice
• Grosor (teoría de grafos) , el número más pequeño de grafos planos en los que se pueden dividir los bordes de un grafo dado
• Planarity , un juego de ordenador de tipo rompecabezas en el que el objetivo es incrustar un gráfico plano en un plano.
• Sprouts (juego) , un juego de lápiz y papel en el que se construye un gráfico plano sujeto a ciertas restricciones como parte del juego.
• Problema de las tres utilidades , un rompecabezas popular

• Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fundamenta Mathematicae (en francés), 15 : 271–283, doi : 10.4064/fm-15-1-271-283.
• Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (en alemán), 114 : 570–590, doi :10.1007/BF01594196, S2CID  123534907.
• Boyer, John M.; Myrvold, Wendy J. (2005), "A la vanguardia: planaridad O(n) simplificada mediante la adición de aristas" (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241–273, doi : 10.7155/jgaa.00091.
• McKay, Brendan ; Brinkmann, Gunnar, Un generador de gráficos planares útil.
• de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Árboles de Trémaux y planaridad", International Journal of Foundations of Computer Science , 17 (5): 1017–1029, arXiv : math/0610935 , doi :10.1142/S0129054106004248, S2CID  40107560Número especial sobre dibujo de gráficos.
• Bader, DA ; Sreshta, S. (1 de octubre de 2003), Un nuevo algoritmo paralelo para pruebas de planaridad (informe técnico), Informe técnico UNM-ECE 03-002, archivado desde el original el 16 de marzo de 2016
• Fisk, Steve (1978), "Una breve demostración del teorema del vigilante de Chvátal", Journal of Combinatorial Theory, Serie B , 24 (3): 374, doi :10.1016/0095-8956(78)90059-X.

Wikimedia Commons tiene medios relacionados con Grafos planares .

• Código fuente del algoritmo de planaridad por adición de aristas, versión 1.0: código fuente gratuito en C para la implementación de referencia del algoritmo de planaridad de Boyer-Myrvold, que proporciona un integrador planar combinatorio y un aislador de subgrafos de Kuratowski. Un proyecto de código abierto con licencia gratuita proporciona la versión actual de los algoritmos de planaridad por adición de aristas.
• Implementación pública de una biblioteca y editor de algoritmos de gráficos: biblioteca de algoritmos de gráficos GPL que incluye pruebas de planaridad, incrustador de planaridad y exhibición de subgráficos de Kuratowski en tiempo lineal.
• Herramientas de la biblioteca de gráficos Boost para gráficos planares, incluidas pruebas de planaridad de tiempo lineal, incrustación, aislamiento de subgráficos de Kuratowski y dibujo de líneas rectas.
• 3 Utilidades Rompecabezas y Gráficos Planares
• Modelo de planaridad de NetLogo: versión de NetLogo del juego de John Tantalo