En la teoría de grafos , una rama de las matemáticas , la prueba de planaridad izquierda-derecha o criterio de planaridad de Fraysseix-Rosenstiehl [1] es una caracterización de grafos planares basada en las propiedades de los árboles de búsqueda en profundidad , publicados por de Fraysseix y Rosenstiehl ( 1982 , 1985 ) [2] [3] y utilizado por ellos con Patrice Ossona de Méndez para desarrollar un algoritmo de prueba de planaridad de tiempo lineal . [4] [5] En una comparación experimental de 2003 de seis algoritmos de prueba de planaridad, este fue uno de los algoritmos más rápidos probados. [6]
Bordes T-iguales y T-opuestos
Para cualquier búsqueda en profundidad de un gráfico G , los bordes encontrados cuando el descubrimiento de un vértice por primera vez definen un árbol de búsqueda en profundidad T de G . Este es un árbol Tremaux , lo que significa que los bordes restantes (el coárbol ) cada uno se conectan un par de vértices que están relacionados entre sí como un ancestro y descendiente en T . Hay tres tipos de patrones se pueden utilizar para definir las relaciones entre los dos pares de bordes coárbol, llamado el T -igual y T -frente a las relaciones.
En las siguientes figuras, los nodos circulares simples representan vértices, los nodos circulares dobles representan subárboles, los segmentos retorcidos representan caminos de árboles y los arcos curvos representan aristas cotárboles. La raíz de cada árbol se muestra en la parte inferior de la figura. En la primera figura, los bordes etiquetados y son similares a T , lo que significa que, en los puntos finales más cercanos a la raíz del árbol, ambos estarán en el mismo lado del árbol en cada dibujo plano. En las siguientes dos figuras, los bordes con las mismas etiquetas están opuestos en T , lo que significa que estarán en diferentes lados del árbol en cada dibujo plano.
![]() y son T-iguales | ![]() y son T-opuestos | ![]() y son T-opuestos |
La caracterización
Deje G un grafo y dejar que T sea un árbol de Tremaux G . La gráfica G es plana si y solo si existe una partición de los bordes de los árboles de G en dos clases, de modo que dos bordes cualesquiera pertenezcan a la misma clase si son similares a T y dos bordes cualesquiera pertenezcan a clases diferentes si son T -opuesto.
Esta caracterización inmediatamente conduce a una prueba de planaridad (ineficiente): determinan para todos los pares de bordes si son T -igual o T -frente, forman un gráfico auxiliar que tiene un vértice para cada componente conectado de T -igual bordes y un borde para cada par de bordes opuestos en T , y compruebe si este gráfico auxiliar es bipartito . Hacer que este algoritmo sea eficiente implica encontrar un subconjunto de los pares T- igual y T -opuesto que sea suficiente para llevar a cabo este método sin determinar la relación entre todos los pares de aristas en el gráfico de entrada.
Referencias
- ^ Auer, Christopher; Gleißner, Andreas; Hanauer, Kathrin; Vetter, Sebastian (2013), "Prueba de planaridad cambiando trenes", Dibujo de gráficos: 20º Simposio Internacional, GD 2012, Redmond, WA, EE. UU., 19-21 de septiembre de 2012, Artículos seleccionados revisados , Lecture Notes in Computer Science, 7704 , Berlín: Springer, págs. 557–558, doi : 10.1007 / 978-3-642-36763-2_51.
- ^ de Fraysseix, H .; Rosenstiehl, P. (1982), "Una caracterización de planaridad de búsqueda en profundidad primero", Graph Theory (Cambridge, 1981) , Annals of Discrete Mathematics, 13 , North-Holland, Amsterdam-New York, pp. 75-80, Señor 0671906.
- ^ de Fraysseix, H .; Rosenstiehl, P. (1985), "Una caracterización de gráficos planos por órdenes de Trémaux", Combinatorica , 5 (2): 127-135, doi : 10.1007 / BF02579375 , MR 0815578.
- ^ de Fraysseix, Hubert; Ossona de Méndez, Patrice ; Rosenstiehl, Pierre (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science , 17 (5): 1017–1029, arXiv : math.CO/0610935 , doi : 10.1142 / S0129054106004248 , MR 2270949.
- ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice (2012), "Trémaux trees and planarity", European Journal of Combinatorics , 33 (3): 279-293, arXiv : math / 0610935 , doi : 10.1016 / j.ejc.2011.09.012 , MR 2864415.
- ^ Boyer, John M .; Cortese, Pier Francesco; Patrignani, Maurizio; Di Battista, Giuseppe (2004), "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 simple", Dibujo gráfico: 11º Simposio Internacional, GD 2003 Perugia, Italia, 21-24 de septiembre de 2003 , Revised Papers , Lecture Notes in Computer Science, 2912 , Berlín: Springer, págs. 25–36, doi : 10.1007 / 978-3-540-24595-7_3 , MR 2177580.
Otras lecturas
- Kaiser, Daniel (2009), Implementation und Animation des Links-Rechts-Planaritätstests , Bachelorarbeit (en alemán), Universidad de Konstanz , FB Informatik und Informationswissenschaft