En teoría de grafos , un gráfico plano es un gráfico que puede incrustarse en el plano , es decir, que puede dibujarse en el plano de tal manera que sus aristas se intersequen sólo en sus puntos finales. En otras palabras, se puede dibujar de tal manera que ningún borde se cruce. [1] [2] Un dibujo de este tipo se denomina gráfico plano o incrustación plana del gráfico . Un gráfico plano se puede definir como un gráfico plano con un mapeo de cada nodo a un punto en un plano, y de cada borde a una curva plana en ese plano, de modo que los puntos extremos de cada curva son los puntos mapeados desde su extremo. nodos, y todas las curvas son disjuntas excepto en sus puntos extremos.
Todo gráfico que se puede dibujar en un plano también se puede dibujar en la esfera , y viceversa, mediante proyección estereográfica .
Los gráficos planos se pueden codificar mediante mapas combinatorios o sistemas de rotación .
Una clase de equivalencia de dibujos topológicamente equivalentes en la esfera, generalmente con suposiciones adicionales como la ausencia de istmos , se llama mapa plano . Aunque un gráfico plano tiene una cara externa o ilimitada , ninguna de las caras de un mapa plano tiene un estatus particular.
Los gráficos planos se generalizan a gráficos dibujables sobre una superficie de un género determinado . En esta terminología, los gráficos planos tienen género 0, ya que el plano (y la esfera) son superficies de género 0. Consulte " incrustación de gráficos " para otros temas relacionados.
El matemático polaco Kazimierz Kuratowski proporcionó una caracterización de los gráficos planos en términos de gráficos prohibidos , hoy conocido como teorema de Kuratowski :
Una subdivisión de un gráfico 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 de menores :
Un menor de un gráfico resulta de tomar un subgrafo y contraer repetidamente un borde en un vértice, donde cada vecino de los vértices finales originales se convierte en vecino del nuevo vértice.
Klaus Wagner preguntó de manera más general si cualquier clase de grafos cerrados 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 5 y K 3,3 son los menores prohibidos para la clase de grafos planos finitos.
En la práctica, es difícil utilizar el criterio de Kuratowski para decidir rápidamente si una gráfica determinada es plana. Sin embargo, existen algoritmos rápidos para este problema: para un gráfico con n vértices, es posible determinar en el tiempo O ( n ) (tiempo lineal) si el gráfico puede ser plano o no (ver prueba de planaridad ).
Para un gráfico plano, simple y conectado con v vértices, e aristas y f caras, se cumplen las siguientes condiciones simples para v ≥ 3 :
En este sentido, los gráficos planos son gráficos dispersos , en el sentido de que tienen solo aristas O ( v ) , asintóticamente más pequeñas que el máximo O ( v 2 ) . El gráfico K 3,3 , 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 plano. Estos teoremas proporcionan condiciones necesarias para la planaridad que no son condiciones suficientes y, por lo tanto, sólo pueden usarse para demostrar que una gráfica no es plana, no que sea plana. Si fallan tanto el teorema 1 como el 2, se pueden utilizar otros métodos.
La fórmula de Euler establece que si se dibuja un gráfico plano , 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, incluidas la región exterior, infinitamente grande), entonces
A modo de ilustración, en el gráfico de mariposa mostrado anteriormente, v = 5 , e = 6 y f = 3 . En general, si la propiedad se cumple para todas las gráficas planas de f caras, cualquier cambio en la gráfica que cree una cara adicional mientras se mantiene la gráfica plana mantendría v – e + f invariante. Dado que la propiedad se cumple para todas las gráficas 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 se elimina una arista que completa 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 , lo que produce v – e + f = 2 , es decir, la característica de Euler es 2.
En un gráfico 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; Usando la fórmula de Euler, se puede demostrar que estas gráficas son dispersas en el sentido de que si v ≥ 3 :
La fórmula de Euler también es válida para poliedros convexos . Esto no es una coincidencia: cada poliedro convexo se puede convertir en un gráfico plano, simple y conexo utilizando el diagrama de Schlegel del poliedro, una proyección en perspectiva del poliedro sobre un plano con el centro de perspectiva elegido cerca del centro de uno de los caras del poliedro. No todos los grafos planos corresponden de esta manera a un poliedro convexo: los árboles, por ejemplo, no. El teorema de Steinitz dice que los gráficos poliédricos formados a partir de poliedros convexos son precisamente los gráficos planos simples finitos de 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 gráficos planos conectados con más de una arista obedecen a la desigualdad 2 e ≥ 3 f , porque cada cara tiene al menos tres incidencias entre cara y arista y cada arista contribuye exactamente con dos incidencias. A través de transformaciones algebraicas de esta desigualdad con la fórmula de Euler v - e + f = 2 se deduce que para gráficos planos finitos el grado promedio es estrictamente menor que 6. Los gráficos con un grado promedio más alto no pueden ser planos.
Decimos que dos círculos dibujados en un plano se besan (u osculan ) siempre que se cruzan exactamente en un punto. Un "gráfico de monedas" es un gráfico formado por un conjunto de círculos, de los cuales no hay dos que tengan interiores superpuestos, creando un vértice para cada círculo y un borde para cada par de círculos que se besan. El teorema del empaquetamiento circular , demostrado por primera vez por Paul Koebe en 1936, establece que una gráfica es plana si y sólo si es una gráfica de moneda.
Este resultado proporciona una prueba sencilla del teorema de Fáry , de que todo gráfico plano simple puede incrustarse en el plano de tal manera que sus aristas sean segmentos de recta que no se cruzan entre sí. Si uno coloca cada vértice del gráfico en el centro del círculo correspondiente en una representación de gráfico de monedas, entonces los segmentos de línea entre los centros de los círculos que se besan no cruzan ninguno de los otros bordes.
El coeficiente de mallado o densidad D de un gráfico plano, o red, es la relación entre el número f – 1 de caras acotadas (el mismo que el rango del circuito del gráfico, según el criterio de planaridad de Mac Lane ) entre sus valores máximos posibles 2 v – 5 para un gráfico con v vértices:
La densidad obedece a 0 ≤ D ≤ 1 , con D = 0 para un gráfico plano completamente disperso (un árbol) y D = 1 para un gráfico plano completamente denso (máximo). [3]
Dada una incrustación G de un gráfico conectado (no necesariamente simple) en el plano sin intersecciones de aristas, construimos el gráfico 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 modo que cruce a e exactamente una vez y que no se cruce ninguna otra arista de G o G* . Entonces G* es nuevamente la incorporación de un gráfico plano (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 incrustaciones en la esfera . Si G es el gráfico plano correspondiente a un poliedro convexo, entonces G* es el gráfico plano 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 probar resultados sobre 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 homeomórficas ).
Un gráfico simple se llama plano máximo si es plano, pero agregar cualquier arista (en el conjunto de vértices dado) destruiría esa propiedad. Todas las caras (incluida la exterior) están limitadas por tres aristas, lo que explica el término alternativo triangulación plana . También se han utilizado los nombres alternativos "gráfico triangular" [4] o "gráfico triangular" [5] , pero son ambiguos, ya que se refieren más comúnmente al gráfico lineal de un gráfico completo y a los gráficos cordales , respectivamente. Todo gráfico plano máximo tiene al menos 3 conexos.
Si un gráfico plano máximo tiene v vértices con v > 2 , entonces tiene precisamente 3 v – 6 aristas y 2 v – 4 caras.
Las redes apolíneas son gráficos planos máximos formados al dividir repetidamente caras triangulares en triples de triángulos más pequeños. De manera equivalente, son los 3 árboles planos .
Las gráficas estranguladas son aquellas en las que cada ciclo periférico es un triángulo. En un gráfico plano máximo (o más generalmente un gráfico poliédrico), los ciclos periféricos son las caras, por lo que los gráficos planos máximos están estrangulados. Los gráficos estrangulados incluyen también los gráficos cordales , y son exactamente los gráficos que pueden formarse mediante sumas de camarillas (sin eliminar aristas) de gráficos completos y gráficos planos máximos. [6]
Los gráficos externos son gráficos con una incrustación en el plano de modo que todos los vértices pertenecen a la cara ilimitada de la incrustación. Todo grafo plano exterior es plano, pero lo contrario no es cierto: K 4 es plano pero no plano exterior. Un teorema similar al de Kuratowski establece que un grafo finito es plano exterior si y sólo si no contiene una subdivisión de K 4 o de K 2,3 . Lo anterior es un corolario directo del hecho de que un gráfico G es plano externo si el gráfico formado a partir de G agregando un nuevo vértice, con aristas que lo conectan a todos los demás vértices, es un gráfico plano. [7]
Una incrustación de un gráfico en un plano exterior es lo mismo que una incrustación en un plano exterior. Para k > 1, una incrustación plana es k -planar exterior si la eliminación de los vértices de la cara exterior da como resultado una incrustación ( k – 1) -planar exterior. Un gráfico es k -planar exterior si tiene una incrustación k -planar exterior.
Un gráfico de Halin es un gráfico 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. De manera equivalente, es un gráfico poliédrico en el que una cara es adyacente a todas las demás. Todo gráfico de Halin es plano. Al igual que los gráficos planos externos, los gráficos de Halin tienen un ancho de árbol bajo , lo que hace que muchos problemas algorítmicos se resuelvan más fácilmente que en los gráficos planos sin restricciones. [8]
Un gráfico plano ascendente es un gráfico acíclico dirigido que se puede dibujar en el plano con sus bordes como curvas que no se cruzan y que están consistentemente orientadas en dirección ascendente. No todos los gráficos acíclicos dirigidos planos son planos hacia arriba, y es NP-completo probar si un gráfico dado es plano hacia arriba.
Se dice que un gráfico plano es convexo si todas sus caras (incluida la cara exterior) son polígonos convexos . No todos los gráficos planos tienen una incrustación convexa (por ejemplo, el gráfico bipartito completo K 2,4 ). Una condición suficiente para que un gráfico pueda dibujarse convexamente es que sea una subdivisión de un gráfico plano conectado con 3 vértices . El teorema del resorte de Tutte incluso establece que para gráficos planos simples conectados con 3 vértices, la posición de los vértices internos se puede elegir para que sea el promedio de sus vecinos.
Los gráficos planos representables con palabras incluyen gráficos planos sin triángulos y, más generalmente, gráficos planos de 3 colores, [9] así como ciertas subdivisiones de caras de gráficos de cuadrícula triangular, [10] y ciertas triangulaciones de gráficos cilíndricos cubiertos de cuadrícula. [11]
La asintótica para el número de gráficos planos (etiquetados) en los vértices es , donde y . [12]
Casi todos los gráficos planos tienen un número exponencial de automorfismos. [13]
El número de gráficos planos sin etiquetar (no isomorfos) en los vértices está entre y . [14]
El teorema de los cuatro colores establece que todo gráfico plano se puede colorear en 4 colores (es decir, en 4 partes).
El teorema de Fáry establece que todo grafo plano simple admite una representación como un grafo plano rectilíneo . Un conjunto de puntos universal es un conjunto de puntos tal que cada gráfico plano con n vértices tiene tal incrustación con todos los vértices del conjunto de puntos; Existen conjuntos de puntos universales de tamaño cuadrático, formados tomando un subconjunto rectangular de la red de números enteros . Cada gráfico plano exterior simple admite una incrustación en el plano de modo que todos los vértices se encuentran en un círculo fijo y todos los bordes son segmentos de línea recta que se encuentran dentro del disco y no se cruzan, por lo que los polígonos regulares de n -vértices son universales para los gráficos planos exteriores.
La conjetura de Scheinerman (ahora un teorema) establece que cada gráfico plano se puede representar como un gráfico de intersección de segmentos de línea en el plano.
El teorema del separador plano establece que cada gráfico plano de n -vértices se puede dividir en dos subgrafos de tamaño como máximo 2 n /3 mediante la eliminación de O ( √ n ) vértices. Como consecuencia, los gráficos planos también tienen ancho de árbol y ancho de rama O ( √ n ).
El teorema de la estructura del producto plano establece que cada gráfico plano es un subgrafo del producto del gráfico fuerte de un gráfico de ancho de árbol como máximo 8 y una ruta. [15] Este resultado se ha utilizado para mostrar que los gráficos planos tienen un número de cola acotado , un número cromático no repetitivo acotado y gráficos universales de tamaño casi lineal. También tiene aplicaciones para la clasificación de vértices [16] y la coloración centrada en p [17] de gráficos planos.
Para dos gráficos planos con v vértices, es posible determinar en el tiempo O ( v ) si son isomorfos o no (ver también problema de isomorfismo gráfico ). [18]
Cualquier gráfico plano en n nodos tiene como máximo 8 (n-2) camarillas máximas, [19] lo que implica que la clase de gráficos planos es una clase con pocas camarillas.
Un gráfico de vértice es un gráfico que puede volverse plano eliminando un vértice, y un gráfico de k -ápice es un gráfico que puede volverse plano eliminando como máximo k vértices.
Un gráfico uniplanar es un gráfico que se puede dibujar en el plano con como máximo un cruce simple por arista, y un gráfico k -planar es un gráfico que se puede dibujar con como máximo k cruces simples por arista.
Un gráfico de mapa es un gráfico formado a partir de un conjunto de un número finito de regiones interiores disjuntas simplemente conectadas en el plano conectando 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 gráfico plano, pero cuando cuatro o más regiones se encuentran en un punto, el resultado puede ser no plano (por ejemplo, si uno piensa en un círculo dividido en sectores, con los sectores siendo las regiones, entonces el gráfico del mapa correspondiente es el gráfico completo ya que todos los sectores tienen un punto límite común (el punto central).
Un gráfico toroidal es un gráfico que se puede incrustar sin cruces en el toroide . De manera más general, el género de un gráfico es el género mínimo de una superficie bidimensional en la que se puede incrustar el gráfico; los gráficos planos tienen género cero y los gráficos toroidales no planos tienen género uno. Cada gráfico puede incrustarse sin cruces en alguna superficie bidimensional cerrada (orientable, conectada) (esfera con asas) y, por lo tanto, el género de un gráfico está bien definido. Obviamente, si el gráfico se puede incrustar sin cruces en una superficie (orientable, conectada, cerrada) con género g, se puede incrustar sin cruces en todas las superficies (orientables, conectadas, cerradas) con género mayor o igual. También hay otros conceptos en teoría de grafos que se denominan "género X" con algún calificativo "X"; en general, estos difieren del concepto de "género" definido anteriormente sin ningún calificativo. Especialmente el género no orientable de un gráfico (que usa superficies no orientables en su definición) es diferente para un gráfico general del género de ese gráfico (que usa superficies orientables en su definición).
Cualquier gráfico puede incrustarse en un espacio tridimensional sin cruces. De hecho, cualquier gráfico se puede dibujar sin cruces en una configuración de dos planos, donde dos planos se colocan uno encima del otro y se permite que los bordes "salten" y "desciendan" 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 realizar 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 la parte superior del tablero se logra a través de trozos de alambre y en la parte inferior mediante pistas de cobre construidas sobre el propio tablero y la conexión eléctrica entre los lados del tablero se logra mediante la perforación de orificios, pasando los cables a través de los orificios y soldándolos . en las vías); También se puede interpretar esto como que para construir cualquier red de carreteras, sólo se necesitan puentes o túneles, no ambos (2 niveles son suficientes, 3 no son necesarios). Además, en tres dimensiones la cuestión de dibujar la gráfica sin cruces es trivial. Sin embargo, los gráficos integrables sin enlaces proporcionan un análogo tridimensional de los gráficos planos , gráficos que se pueden incrustar en un espacio tridimensional de tal manera que no hay dos ciclos topológicamente vinculados entre sí. En analogía con las caracterizaciones de Kuratowski y Wagner de los gráficos planos como los gráficos que no contienen K 5 o K 3,3 como menor, los gráficos integrables sin enlaces pueden caracterizarse como los gráficos que no contienen como menor ninguno de los Siete gráficos en la familia Petersen . En analogía con las caracterizaciones de los gráficos planos externos y planos como gráficos con el gráfico de Colin de Verdière invariante como máximo dos o tres, los gráficos integrables sin enlaces son los gráficos que tienen a Colin de Verdière invariante como máximo cuatro.
Así, un gráfico plano, cuando se dibuja sobre una superficie plana, no tiene cruces de aristas o se puede volver a dibujar sin ellas.
