Prueba de planaridad izquierda-derecha
En la teoría de grafos , una rama de las matemáticas , la prueba de planaridad de izquierda a derecha o el criterio de planaridad de Fraysseix-Rosenstiehl [1] es una caracterización de los gráficos planos 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]
Para cualquier búsqueda en profundidad de un gráfico G , los bordes encontrados al descubrir un vértice por primera vez definen un árbol de búsqueda en profundidad T de G . Este es un árbol de Trémaux , lo que significa que los bordes restantes (el coárbol ) conectan cada uno un par de vértices que están relacionados entre sí como un antepasado y un descendiente en T. Se pueden usar tres tipos de patrones para definir dos relaciones entre pares de aristas del coárbol, denominadas relaciones T -iguales y T -opuestas .
En las siguientes figuras, los nodos de círculo simple representan vértices, los nodos de círculo doble representan subárboles, los segmentos torcidos representan caminos de árbol y los arcos curvos representan bordes de coárbol. La raíz de cada árbol se muestra en la parte inferior de la figura. En la primera figura, los bordes etiquetados y son iguales en 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, las aristas con las mismas etiquetas son T -opuestas, lo que significa que estarán en diferentes lados del árbol en cada dibujo plano.
Sea G un grafo y sea T un árbol de Trémaux de G . El grafo G es plano si y solo si existe una partición de las aristas del coárbol de G en dos clases, de modo que dos aristas cualesquiera pertenezcan a la misma clase si son T -iguales y dos aristas cualesquiera pertenezcan a clases diferentes si son T -opuesto.
Esta caracterización conduce inmediatamente a una prueba de planaridad (ineficiente): determinar para todos los pares de aristas si son T -igual o T - opuestas, formar un gráfico auxiliar que tenga un vértice para cada componente conectado de T -igual a las aristas y una arista para cada par de aristas T -opuestas, y comprueba si este grafo auxiliar es bipartito . Hacer que este algoritmo sea eficiente implica encontrar un subconjunto de pares T iguales y T opuestos 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.
