En teoría de grafos , el problema de prueba de planaridad es el problema algorítmico de probar si un gráfico dado es un gráfico plano (es decir, si se puede dibujar en el plano sin intersecciones de bordes). Este es un problema bien estudiado en informática para el que han surgido muchos algoritmos prácticos, muchos de los cuales aprovechan las estructuras de datos novedosas . La mayoría de estos métodos operan en tiempo O ( n ) (tiempo lineal), donde n es el número de aristas (o vértices) en el gráfico, que es asintóticamente óptimo.. En lugar de ser solo un valor booleano único, la salida de un algoritmo de prueba de planaridad puede ser una incrustación de gráfico plano , si el gráfico es plano, o un obstáculo para la planaridad, como un subgráfico de Kuratowski, si no lo es.
Criterios de planaridad
Los algoritmos de prueba de planaridad suelen aprovechar los teoremas de la teoría de grafos que caracterizan el conjunto de gráficos planos en términos que son independientes de los dibujos de gráficos. Éstas incluyen
- El teorema de Kuratowski de que un grafo es plano si y solo si no contiene un subgrafo que sea una subdivisión de K 5 (el grafo completo en cinco vértices ) o K 3,3 (el grafo de utilidad , un grafo bipartito completo en seis vértices, tres de los cuales se conectan a cada uno de los otros tres).
- El teorema de Wagner de que un gráfico es plano si y solo si no contiene un subgrafo menor (subgrafo de una contracción) que es isomorfo a K 5 o K 3,3 .
- El criterio de planaridad de Fraysseix-Rosenstiehl , que caracteriza gráficas planas en términos de un orden de izquierda a derecha de los bordes en un árbol de búsqueda en profundidad .
El criterio de planaridad de Fraysseix-Rosenstiehl se puede utilizar directamente como parte de los algoritmos para la prueba de planaridad, mientras que los teoremas de Kuratowski y Wagner tienen aplicaciones indirectas: si un algoritmo puede encontrar una copia de K 5 o K 3,3 dentro de un gráfico dado, puede ser asegúrese de que el gráfico de entrada no sea plano y vuelva sin cálculos adicionales.
Otros criterios de planaridad, que caracterizan matemáticamente las gráficas planas pero son menos centrales para los algoritmos de prueba de planaridad, incluyen:
- El criterio de planaridad de Whitney de que una gráfica es plana si y solo si su matriz gráfica también es cográfica,
- El criterio de planaridad de Mac Lane que caracteriza gráficas planas por las bases de sus espacios cíclicos ,
- El teorema de Schnyder que caracteriza gráficas planas por la dimensión de orden de un orden parcial asociado , y
- Criterio de planaridad de Colin de Verdière utilizando la teoría de grafos espectrales .
Algoritmos
Método de adición de ruta
El método clásico de adición de ruta de Hopcroft y Tarjan [1] fue el primer algoritmo de prueba de planaridad en tiempo lineal publicado en 1974. Una implementación del algoritmo de Hopcroft y Tarjan se proporciona en la Biblioteca de tipos y algoritmos de datos eficientes de Mehlhorn , Mutzel y Näher [2] [3] . [4] En 2012, Taylor [5] amplió este algoritmo para generar todas las permutaciones de orden de borde cíclico para incrustaciones planas de componentes biconnectados.
Método de suma de vértices
Los métodos de suma de vértices funcionan manteniendo una estructura de datos que representa las posibles incrustaciones de un subgráfico inducido del gráfico dado y agregando vértices uno a la vez a esta estructura de datos. Estos métodos comenzaron con un método ineficiente O ( n 2 ) concebido por Lempel , Even y Cederbaum en 1967. [6] Fue mejorado por Even y Tarjan, quienes encontraron una solución de tiempo lineal para el paso de numeración s , t , [ 7] y por Booth y Lueker , quienes desarrollaron la estructura de datos del árbol PQ . Con estas mejoras, es de tiempo lineal y en la práctica supera al método de suma de rutas. [8] Este método también se amplió para permitir que una incrustación plana (dibujo) se calcule de manera eficiente para un gráfico plano. [9] En 1999, Shih y Hsu simplificaron estos métodos utilizando el árbol de PC (una variante sin raíz del árbol PQ) y un recorrido postorder del árbol de búsqueda en profundidad de los vértices. [10]
Método de adición de bordes
En 2004, John Boyer y Wendy Myrvold [11] desarrollaron un algoritmo O ( n ) simplificado , originalmente inspirado en el método del árbol PQ, que elimina el árbol PQ y usa adiciones de bordes para calcular una incrustación plana, si es posible. De lo contrario, se calcula una subdivisión de Kuratowski (de K 5 o K 3,3 ). Este es uno de los dos algoritmos más actuales en la actualidad (el otro es el algoritmo de prueba de planaridad de de Fraysseix, de Mendez y Rosenstiehl [12] [13] ). Ver [14] para una comparación experimental con una versión preliminar de la prueba de planaridad de Boyer y Myrvold. Además, la prueba de Boyer-Myrvold se amplió para extraer múltiples subdivisiones de Kuratowski de un gráfico de entrada no plano en un tiempo de ejecución que depende linealmente del tamaño de salida. [15] El código fuente para la prueba de planaridad [16] [17] y la extracción de múltiples subdivisiones de Kuratowski [16] está disponible públicamente. Los algoritmos que ubican un subgrafo de Kuratowski en tiempo lineal en vértices fueron desarrollados por Williamson en la década de 1980. [18]
Método de secuencia de construcción
Un método diferente utiliza una construcción inductiva de gráficos conectados en 3 para construir incrustaciones planas de cada componente de G con 3 conexiones (y, por lo tanto, una incrustación plana de G ). [19] La construcción comienza con K 4 y se define de tal manera que cada gráfico intermedio en el camino hacia el componente completo está nuevamente conectado en 3. Dado que tales gráficos tienen una incrustación única (hasta el giro y la elección de la cara externa), el siguiente gráfico más grande, si aún es plano, debe ser un refinamiento del gráfico anterior. Esto permite reducir la prueba de planaridad a solo probar para cada paso si el siguiente borde agregado tiene ambos extremos en la cara externa de la incrustación actual. Si bien esto es conceptualmente muy simple (y proporciona un tiempo de ejecución lineal), el método en sí mismo adolece de la complejidad de encontrar la secuencia de construcción.
Referencias
- ^ Hopcroft, John ; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery , 21 (4): 549–568, doi : 10.1145 / 321850.321852 , hdl : 1813/6011.
- ^ Mehlhorn, Kurt; Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm", Algorithmica , 16 (2): 233–242, doi : 10.1007 / bf01940648 , hdl : 11858 / 00-001M-0000-0014 -B51D-B
- ^ Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), una implementación de la prueba de planaridad de Hopcroft y Tarjan y el algoritmo de incrustación
- ^ Mehlhorn, Kurt; Näher, Stefan (1995), "LEDA: A library of eficientes tipos de datos y algoritmos", Communications of the ACM , 38 (1): 96–102, CiteSeerX 10.1.1.54.9556 , doi : 10.1145 / 204865.204889
- ^ Taylor, Martyn G. (2012). Prueba de planaridad por adición de ruta (Ph.D.). Universidad de Kent. Archivado desde el original el 5 de marzo de 2016. URL alternativa
- ^ Lempel, A .; Incluso, S .; Cederbaum, I. (1967), "Un algoritmo para la prueba de planaridad de gráficos", en Rosenstiehl, P. (ed.), Theory of Graphs , Nueva York: Gordon y Breach, págs. 215-232.
- ^ Incluso, Shimon; Tarjan, Robert E. (1976), "Computing an st -numbering", Theoretical Computer Science , 2 (3): 339–344, doi : 10.1016 / 0304-3975 (76) 90086-4.
- ^ Boyer y Myrvold (2004) , p. 243: "Su implementación en LEDA es más lenta que las implementaciones LEDA de muchos otrosalgoritmos de planaridad en tiempoO ( n )".
- ^ Chiba, N .; Nishizeki, T .; Una abeja.; Ozawa, T. (1985), "Un algoritmo lineal para incrustar gráficos planos utilizando árboles PQ", Journal of Computer and System Sciences , 30 (1): 54–76, doi : 10.1016 / 0022-0000 (85) 90004- 2.
- ^ Shih, WK; Hsu, WL (1999), "A new planarity test", Theoretical Computer Science , 223 (1-2): 179-191, doi : 10.1016 / S0304-3975 (98) 00120-0.
- ^ Boyer, John M .; Myrvold, Wendy J. (2004), "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.
- ^ 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–1030, arXiv : math / 0610935 , doi : 10.1142 / S0129054106004248.
- ^ Brandes, Ulrik (2009), La prueba de planaridad izquierda-derecha (PDF).
- ^ Boyer, John M .; Cortese, PF; Patrignani, M .; Battista, GD (2003), "Deje de preocuparse por sus P y Q: implementación de un algoritmo de incrustación y prueba de planaridad basado en DFS rápido y sencillo", Proc. 11 ° Int. Symp. Graph Drawing (GD '03) , Lecture Notes in Computer Science , 2912 , Springer-Verlag, págs. 25–36
- ^ Chimani, M .; Mutzel, P .; Schmidt, JM (2008), "Extracción eficiente de múltiples subdivisiones de Kuratowski", Proc. 15 ° Int. Symp. Graph Drawing (GD'07) , Lecture Notes in Computer Science, 4875 , Sydney, Australia: Springer-Verlag, págs. 159-170.
- ^ a b "OGDF - Marco de dibujo de gráfico abierto: Inicio" .
- ^ "Biblioteca de gráficos de impulso: incrustación / prueba de planaridad de Boyer-Myrvold - 1.40.0" .
- ^ Williamson, SG (1984), "Depth First Search y Kuratowski Subgraphs", Journal of the ACM , 31 (4): 681–693, doi : 10.1145 / 1634.322451
- ^ Schmidt, Jens M. (2014), Autómatas, lenguajes y programación , Lecture Notes in Computer Science, 8572 , págs. 967–978, doi : 10.1007 / 978-3-662-43948-7_80 , ISBN 978-3-662-43947-0 Parámetro desconocido
|conference=
ignorado ( ayuda )