¿Cuál es el algoritmo polinomial más simple para PLANARITY?

Hay varios algoritmos que deciden en tiempo polinómico si un gráfico se puede dibujar en el plano o no, incluso muchos con un tiempo de ejecución lineal. Sin embargo, no pude encontrar un algoritmo muy simple que uno pudiera explicar fácil y rápidamente en clase y mostrara que PLANARITY está en P. ¿Conoces alguno?

Si es necesario, puede usar el teorema de Kuratowski o Fary, pero no cosas profundas, como el teorema menor del gráfico. También tenga en cuenta que no me importa el tiempo de ejecución, solo quiero algo polinomial.

A continuación se muestran los 3 mejores algoritmos hasta el momento, que muestran una compensación simple / sin teoría profunda.

Algoritmo 1: Utilizando eso podemos verificar si un gráfico contiene un o un como menor en tiempo polinómico, obtenemos un algoritmo muy simple usando la teoría profunda. (Tenga en cuenta que esta teoría ya usa incrustaciones de gráficos, como lo señala Saeed, por lo que este no es un enfoque algorítmico real, solo algo simple para decirles a los estudiantes que ya sabían / ​​aceptaron el teorema menor del gráfico).K 3 , $K_5$$K_{3,3}$

Algoritmo 2 [basado en la respuesta de alguien]: es fácil ver que es suficiente para lidiar con gráficos conectados a 3. Para estos, encuentre una cara y luego aplique el teorema de primavera de Tutte.

Algoritmo 3 [recomendado por Juho]: algoritmo Demoucron, Malgrange y Pertuiset (DMP). Dibuje un ciclo, los componentes del gráfico restante se denominan fragmentos, los incrustamos de manera adecuada (mientras creamos nuevos fragmentos). Este enfoque no utiliza otros teoremas.

Voy a describir un algoritmo. No estoy seguro de que califique como "fácil" y algunas de las pruebas no son tan fáciles.

Primero dividimos el gráfico en 3 componentes conectados, como lo menciona Chandra Chekuri.

1. Divide el gráfico en componentes conectados.
2. Divide cada componente conectado en 2 componentes conectados. Esto se puede hacer en tiempo polinómico comprobando para cada vértice de cada componente 2 conectado si está conectado.G i G i - $v$$G_i$$G_i-v$
3. Divide cada componente conectado a 2 en componentes conectados a 3. Esto se puede hacer en tiempo polinómico comprobando dos vértices distintos de cada componente 2 conectado si está conectado.G i G i - { v , u $v,u$$G_i$$G_i-\{ v,u \}$

Hemos reducido el problema a verificar si un componente del gráfico conectado a 3 es plano. Deje denotar un componente de 3 conectados.$G$

1. Tome cualquier ciclo de .$C$$G$
2. Fija los vértices de como vértices de un polígono convexo. Coloque cada uno de los otros vértices en el baricentro de sus vecinos. Esto lleva a un sistema de ecuaciones lineales que indican las coordenadas de cada vértice. Deje ser el dibujo resultante; Puede tener cruces.$C$$D$
3. Si no tiene cruces, hemos terminado.$D$
4. Tome los vértices en cualquier componente conectado de . La restricción de al subgrafo inducido debe ser plana. De lo contrario, no es plano. Tome cualquier cara en el dibujo restringido al subgrafo inducido , y dejar que sea el ciclo de la definición de . Si debe ser plano, entonces debe ser un ciclo facial. (Cuando es un ciclo hamiltoniano, entonces debe construirse usando una arista).G - V ( C ) D G [ U ∪ V ( C ) ] G F D G [ U ∪ V ( C ) ] C ′ F G C ′ C C $U$$G-V(C)$$D$$G[U\cup V(C)]$$G$$F$$D$$G[U\cup V(C)]$$C'$$F$$G$$C'$$C$$C'$
5. Repita el paso 2 con C 'en lugar de C. Si el dibujo resultante es plano, entonces es plano. Else no es plano.$G$$G$

Observaciones:

• Argumentar que la incrustación de primavera de Tutte da una incrustación plana no es sencillo. Me gustó la presentación en el libro de Edelsbrunner y Harer, Topología computacional, pero es solo para triangulaciones. Colin de Verdiere discute la incrustación de primavera en http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , sección 1.4. Una referencia general es Linial, Lovász, Wigderson: bandas de goma, incrustaciones convexas y conectividad gráfica. Combinatorica 8 (1): 91-102 (1988).
• Resolver un sistema lineal de ecuaciones en un número poliomial de operaciones aritméticas es fácil a través de la eliminación gaussiana. Resolverlo usando un número de bits polionómico no es tan fácil.

El algoritmo de Boyer y Myrvold se considera entre los algoritmos de prueba de planaridad más avanzados.

En la vanguardia: planaridad O (n) simplificada por Edge Addition por Boyer y Myrvold.

Este capítulo del libro examina muchos algoritmos de prueba de planaridad y esperamos que encuentre un algoritmo lo suficientemente simple.

¿Qué pasa con el algoritmo Hopcroft y Tarjan de 1974 {1} ?

{1} Hopcroft, John y Robert Tarjan. "Pruebas de planaridad eficientes". Revista de la ACM (JACM) 21.4 (1974): 549-568.

Dos algoritmos, ambos en LogSpace

1. Eric Allender y Meena Mahajan - La complejidad de las pruebas de planaridad
2. Samir Datta y Gautam Prakriya - Revisar las pruebas de planaridad

El segundo es mucho más simple que el primero.