Gráficos de ejemplo | |
---|---|
Planar | No planar |
Gráfico de mariposa | Gráfico completo K 5 |
Gráfico completo K 4 | Gráfico 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 bordes se crucen solo en sus puntos finales. En otras palabras, se puede dibujar de tal manera que ningún borde se cruce entre sí. [1] [2] Este dibujo 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 sus nodos finales, y todas las curvas están disjuntas excepto en sus puntos extremos.
Cada 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 supuestos adicionales como la ausencia de istmos , se denomina mapa plano . Aunque un gráfico plano tiene una cara externa o ilimitada , ninguna de las caras de un mapa plano tiene un estado particular.
Las gráficas planas se generalizan a gráficas que se pueden dibujar en una superficie de un género dado . En esta terminología, los gráficos planos tienen género 0, ya que el plano (y la esfera) son superficies del género 0. Consulte " incrustación de gráficos " para otros temas relacionados.
Teoremas de Kuratowski y Wagner
El matemático polaco Kazimierz Kuratowski proporcionó una caracterización de gráficos planos en términos de gráficos prohibidos , ahora conocido como teorema de Kuratowski :
- Un gráfico finito es plano si y solo si no contiene un subgráfico que sea una subdivisión del gráfico completo K 5 o del gráfico bipartito completo( gráfico 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 trata con menores :
- Un grafo finito es plano si y solo si no tiene o como menor .
Un menor de un gráfico resulta de tomar un subgráfico y contraer repetidamente un borde en un vértice, con cada vecino de los vértices finales originales convirtiéndose en un vecino del nuevo vértice.
Klaus Wagner preguntó de manera más general si alguna clase de gráficos 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, y son los menores prohibidos para la clase de grafos planos finitos.
Otros criterios de planaridad
En la práctica, es difícil utilizar el criterio de Kuratowski para decidir rápidamente si un gráfico determinado es plano. 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 conectado con v vértices ye aristas e y caras f , 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, las gráficas planas son gráficas dispersas , ya que solo tienen aristas O ( v ), asintóticamente más pequeñas que el máximo O ( v 2 ). La gráfica 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, solo se pueden usar para demostrar que una gráfica no es plana, no que es plana. Si ambos teoremas 1 y 2 fallan, se pueden utilizar 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 gráficos planos finitos, a través de sus espacios cíclicos ;
- El criterio de planaridad de Fraysseix-Rosenstiehl proporciona una caracterización basada en la existencia de una bipartición de los bordes 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 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 una gráfica es plana 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 las gráficas planas mediante un sistema de ecuaciones módulo 2.
Fórmula de Euler
La fórmula de Euler establece que si se dibuja un gráfico plano , conectado y finito en el plano sin intersecciones de aristas, y v es el número de vértices, e es el número de aristas yf es el número de caras (regiones delimitadas por aristas, incluyendo la región exterior, infinitamente grande), luego
Como ilustración, en el gráfico de mariposa anterior, v = 5, e = 6 yf = 3. En general, si la propiedad es válida para todos los gráficos planos de f caras, cualquier cambio en el gráfico 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 , elimine un borde 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, dando v - e + f = 2, es decir, la característica de Euler es 2.
En un gráfico plano , simple , conectado y finito, cualquier cara (excepto posiblemente la exterior) está delimitada 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 escasas 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 conectado 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 gráficos planos corresponden a un poliedro convexo de esta manera: los árboles, por ejemplo, no. El teorema de Steinitz dice que las gráficas poliédricas formadas a partir de poliedros convexos son precisamente las gráficas planas simples finitas conectadas a 3 . De manera más general, la fórmula de Euler se aplica a cualquier poliedro cuyas caras son polígonos simples que forman una superficie topológicamente equivalente a una esfera, independientemente de su convexidad.
Grado medio
Los gráficos planos conectados con más de un borde obedecen a la desigualdad , porque cada cara tiene al menos tres incidencias de borde de cara y cada borde contribuye exactamente con dos incidencias. Se sigue a través de transformaciones algebraicas de esta desigualdad con la fórmula de Euler que para gráficas planas finitas el grado promedio es estrictamente menor que 6. Las gráficas con un grado promedio más alto no pueden ser planas.
Gráficos de monedas
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 moneda" es un gráfico formado por un conjunto de círculos, ninguno de los cuales tiene interiores superpuestos, haciendo un vértice para cada círculo y un borde para cada par de círculos que se besan. El teorema del empaquetamiento circular , probado por primera vez por Paul Koebe en 1936, establece que una gráfica es plana si y solo si es una gráfica de moneda.
Este resultado proporciona una prueba fácil del teorema de Fáry , que todo gráfico plano simple se puede incrustar en el plano de tal manera que sus bordes sean segmentos de línea recta que no se crucen 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 moneda, entonces los segmentos de línea entre los centros de los círculos de besos no cruzan ninguno de los otros bordes.
Densidad de gráfico plano
La densidad de un gráfico plano, o red, se define como una relación entre el número de aristas al número de posibles bordes en una red con nodos, dados por un grafo plano , donación . Un grafo plano completamente disperso tiene, alternativamente, un gráfico plano completamente denso tiene
Familias relacionadas de gráficos
Gráficos planos máximos
Un gráfico simple se llama plano máximo 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 delimitadas por tres aristas, lo que explica el término alternativo triangulación del plano . También se han utilizado los nombres alternativos "gráfico triangular" [3] o "gráfico triangular" [4] , pero son ambiguos, ya que se refieren más comúnmente al gráfico lineal de un gráfico completo ya los gráficos cordales, respectivamente. Cada gráfico plano máximo tiene al menos 3 conexiones.
Si una gráfica plana máxima tiene v vértices con v > 2, entonces tiene exactamente 3 v - 6 aristas y 2 v - 4 caras.
Las redes apolíneas son los 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 .
Los gráficos estrangulados son los gráficos en los 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 se estrangulan. Las gráficas estranguladas incluyen también las gráficas cordales , y son exactamente las gráficas que pueden formarse mediante sumas de clique (sin eliminar bordes) de gráficas completas y gráficas planas máximas. [5]
Gráficos planos exteriores
Los gráficos planos exteriores 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. Cada grafo del plano exterior es plano, pero lo contrario no es cierto: K 4 es plano pero no del plano exterior. Un teorema similar al de Kuratowski establece que un grafo finito es de plano exterior si y solo 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 exterior si el gráfico formado a partir de G al agregar un nuevo vértice, con bordes que lo conectan con todos los demás vértices, es un gráfico plano. [6]
Una incrustación de un plano exterior de un gráfico es lo mismo que una incrustación de un plano exterior. Para k > 1, una incrustación plana es k -outerpillarlanar si la eliminación de los vértices de la cara exterior da como resultado una incrustación ( k - 1) -outerpillarlanar. Un gráfico es k -outerpillarlanar si tiene una incrustación k -outerpillarlanar.
Gráficos de Halin
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 el plano incrustado del árbol. De manera equivalente, es un gráfico poliédrico en el que una cara es adyacente a todas las demás. Cada gráfico de Halin es plano. Al igual que los gráficos planos exteriores, 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. [7]
Un gráfico de vértice es un gráfico que se puede hacer plano mediante la eliminación de un vértice, y un gráfico de k- ápice es un gráfico que se puede hacer plano mediante la eliminación de como máximo k vértices.
Un gráfico de 1 plano es un gráfico que se puede dibujar en el plano con como máximo un cruce simple por borde, y un gráfico de k -planar es un gráfico que se puede dibujar con un máximo de k cruces simples por borde.
Un gráfico de mapa es un gráfico formado a partir de un conjunto de un número finito de regiones disjuntas interiores simplemente conectadas 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 gráfico plano, pero cuando cuatro o más regiones se encuentran en un punto, el resultado puede ser no plano.
Un gráfico toroidal es un gráfico que se puede incrustar sin cruces en el toro . 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; las gráficas planas tienen género cero y las gráficas toroidales no planas tienen género uno.
Cualquier gráfico se puede incrustar en un espacio tridimensional sin cruces. Sin embargo, los gráficos incrustables sin enlaces proporcionan un análogo tridimensional de los gráficos planos , gráficos que pueden incrustarse 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 las gráficas planas como gráficas que no contienen K 5 o K 3,3 como menor, las gráficas incrustables sin enlaces pueden caracterizarse como las gráficas que no contienen como menor ninguna de las siete gráficos de la familia Petersen . De manera análoga a las caracterizaciones de los gráficos planos exterior y plano como siendo los gráficos con el gráfico de Colin de Verdière invariante como máximo dos o tres, los gráficos incrustables sin enlaces son los gráficos que tienen a Colin de Verdière invariante como máximo cuatro.
Un gráfico plano hacia arriba 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 orientadas consistentemente en una dirección hacia arriba. No todas las gráficas acíclicas dirigidas planar son planas hacia arriba, y es NP-completo probar si una gráfica dada es planar hacia arriba.
Enumeración de gráficos planos
El asintótico para el número de gráficas planas (etiquetadas) en vértices es , dónde y . [8]
Casi todos los gráficos planos tienen un número exponencial de automorfismos. [9]
El número de gráficos planos no etiquetados (no isomórficos) en vértices está entre y . [10]
Otros hechos y definiciones
El teorema de los cuatro colores establece que cada gráfico plano es 4- colorable (es decir, 4-partitas).
El teorema de Fáry establece que todo gráfico plano simple admite una incrustación en el plano de modo que todos los bordes son segmentos de línea recta que no se cruzan. Un conjunto de puntos universal es un conjunto de puntos tal que cada grafo plano con n vértices tiene tal incrustación con todos los vértices en el 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 grafo plano exterior simple admite una incrustación en el plano de manera 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 grafos planos exteriores.
Dada una incrustación G de un gráfico conectado (no necesariamente simple) en el plano sin intersecciones de bordes, 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 borde e en G introducimos una nueva arista en G * conectando los dos vértices en G * correspondientes a las dos caras en G que se encuentran en e . Además, este borde se dibuja de modo que cruce e exactamente una vez y que ningún otro borde de G o G * se cruce. Entonces G * es nuevamente la incrustación de un gráfico plano (no necesariamente simple); tiene tantas aristas como G , tantos vértices como caras G tiene y tantas caras como vértices G tiene. 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 forma sencilla con las propiedades del gráfico original, lo que permite probar los resultados de los gráficos examinando sus gráficos duales.
Si bien el doble construido para una incrustación particular es único (hasta el isomorfismo ), los gráficos pueden tener duales diferentes (es decir, no isomórficos), obtenidos de incrustaciones diferentes (es decir, no homeomórficas ).
Un gráfico euclidiano es un gráfico en el que los vértices representan puntos en el plano, y a los bordes se les asignan longitudes iguales a la distancia euclidiana entre esos puntos; ver Teoría de grafos geométricos .
Se dice que un gráfico plano es convexo si todas sus caras (incluida la cara exterior) son polígonos convexos . Un gráfico plano se puede dibujar de forma convexa si y solo si es una subdivisión de un gráfico plano conectado a 3 vértices .
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 grafo plano de n -vértices se puede dividir en dos subgráficos 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 ).
Para dos grafos planos 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 ). [11]
El coeficiente de malla de un gráfico plano normaliza su número de caras delimitadas (el mismo que el rango del circuito del gráfico, según el criterio de planaridad de Mac Lane ) dividiéndolo por 2 n - 5, el número máximo posible de caras delimitadas en un gráfico plano. con n vértices. Por lo tanto, varía de 0 para árboles a 1 para gráficos planos máximos. [12]
Las gráficas planas representables por palabras incluyen gráficas planas sin triángulos y, más generalmente, gráficas planas de 3 colores, [13] así como ciertas subdivisiones de caras de gráficas de cuadrículas triangulares, [14] y ciertas triangulaciones de gráficas de cilindros cubiertas por cuadrículas. [15]
Ver también
- 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 al reemplazar cada punto de cruce por un nuevo vértice
- Espesor (teoría de grafos) , el número más pequeño de grafos planos en los que se pueden dividir los bordes de un gráfico dado
- Planarity , un juego de computadora de 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 tres utilidades , un rompecabezas popular
Notas
- ^ Trudeau, Richard J. (1993). Introducción a la teoría de grafos (reedición ampliada y corregida. Ed.). Nueva York: Dover Pub. pag. 64. ISBN 978-0-486-67870-2. Consultado el 8 de agosto de 2012 .
Por lo tanto, un gráfico plano, cuando se dibuja en una superficie plana, no tiene cruces de bordes o se puede volver a dibujar sin ellos.
- ^ Barthelemy, M. (2017). Morfogénesis de redes espaciales . Nueva York: Springer. pag. 6.
- ^ Schnyder, W. (1989), "Gráficos planos y dimensión poset", Order , 5 (4): 323–343, doi : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.
- ^ Bhasker, Jayaram; Sahni, Sartaj (1988), "Un algoritmo lineal para encontrar un dual rectangular de una gráfica triangulada plana", Algorithmica , 3 (1–4): 247–278, doi : 10.1007 / BF01762117 , S2CID 2709057.
- ^ Seymour, PD; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- ^ Felsner, Stefan (2004), "1.4 Gráficos planos exteriores y gráficos geométricos convexos", gráficos y arreglos geométricos , clases avanzadas de matemáticas, Friedr. Vieweg y Sohn, Wiesbaden, págs. 6–7, doi : 10.1007 / 978-3-322-80303-0_1 , ISBN 3-528-06972-4, MR 2061507
- ^ Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, págs. 248-256, doi : 10.1007 / BFb0071635.
- ^ Giménez, Omer; Noy, Marc (2009). "Enumeración asintótica y leyes límite de gráficos planares". Revista de la Sociedad Matemática Estadounidense . 22 (2): 309–329. arXiv : matemáticas / 0501269 . Código Bibliográfico : 2009JAMS ... 22..309G . doi : 10.1090 / s0894-0347-08-00624-3 . S2CID 3353537 .
- ^ McDiarmid, Colin; Steger, Angelika ; Galés, Dominic JA (2005). "Gráficos planos aleatorios". Revista de Teoría Combinatoria, Serie B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . doi : 10.1016 / j.jctb.2004.09.007 .
- ^ Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Schaeffer, G. (2006). "Gráficos planos, a través de árboles y mapas bien ordenados". Gráficos y combinatorios . 22 (2): 185-202. CiteSeerX 10.1.1.106.7456 . doi : 10.1007 / s00373-006-0647-2 . S2CID 22639942 .
- ^ ES Filotti, Jack N. Mayer. Un algoritmo de tiempo polinomial para determinar el isomorfismo de gráficos de género fijo. Actas del 12º Simposio Anual ACM sobre Teoría de la Computación, p.236–243. 1980.
- ^ Buhl, J .; Gautrais, J .; Sole, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Theraulaz, G. (2004), "Eficiencia y robustez en redes de galerías de hormigas", European Physical Journal B , Springer-Verlag, 42 (1): 123-129, Bibcode : 2004EPJB ... 42..123B , doi : 10.1140 / epjb / e2004-00364-9 , S2CID 14975826.
- ^ M. Halldórsson, S. Kitaev y A. Pyatkin. Orientaciones semitransitivas y gráficos representables por palabras, Discr. Apl. Matemáticas. 201 (2016), 164-171.
- ^ TZQ Chen, S. Kitaev y BY Sun. Representabilidad de palabras de subdivisiones de caras de gráficos de cuadrícula triangular, Graphs y Combin. 32 (5) (2016), 1749-1761.
- ^ TZQ Chen, S. Kitaev y BY Sun. Representabilidad de palabras de triangulaciones de gráficos cilíndricos cubiertos por cuadrículas, Discr. Apl. Matemáticas. 213 (2016), 60 a 70.
Referencias
- 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 por adición de bordes" (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241-273, doi : 10.7155 / jgaa .00091.
- McKay, Brendan ; Brinkmann, Gunnar, un útil generador de gráficos planos.
- de Fraysseix, H .; Ossona de Méndez, P .; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science , 17 (5): 1017–1029, arXiv : math / 0610935 , doi : 10.1142 / S0129054106004248 , S2CID 40107560. Número especial sobre dibujo de gráficos.
- DA Bader y S. Sreshta, A New Parallel Algorithm for Planarity Testing , UNM-ECE Technical Report 03-002, 1 de octubre de 2003.
- Fisk, Steve (1978), "Una breve prueba del teorema del vigilante de Chvátal", Journal of Combinatorial Theory, Serie B , 24 (3): 374, doi : 10.1016 / 0095-8956 (78) 90059-X.
enlaces externos
- Código fuente del algoritmo de planaridad de adición de bordes, versión 1.0 : código fuente C gratuito para la implementación de referencia del algoritmo de planaridad de Boyer-Myrvold, que proporciona un embebidor planar combinatorio y un aislador de subgrafo de Kuratowski. Un proyecto de código abierto con licencia gratuita proporciona los algoritmos de planaridad de adición de bordes, la versión actual .
- 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 subgrafos de Kuratowski en tiempo lineal.
- Mejore las herramientas de la biblioteca de gráficos para gráficos planos , que incluyen pruebas de planaridad de tiempo lineal, incrustación, aislamiento de subgrafos de Kuratowski y dibujo en línea recta.
- 3 Utilidades Rompecabezas y gráficos planos
- Modelo NetLogo Planarity : versión NetLogo del juego de John Tantalo