¿Hay algún algoritmo en línea para las pruebas de planaridad?

Question

Sé que prueba de planaridad se puede hacer en O (v) (equivalentemente O (e ), ya que los gráficos planos tienen bordes O (v) bordes).

Me pregunto si se puede hacer en línea en O (1) tiempo amortizado a medida que se agrega cada borde (todavía O (e) tiempo en general).

En otras palabras, en una tabla de base de datos que representa los bordes de un gráfico y está sujeta a una restricción de que el gráfico representado es plano, ¿cuánto tiempo debe tomar el DBMS responsable de administrar la restricción para validar cada inserción propuesta? (Para simplificar, suponga que no hay eliminaciones). ¿Debe volver a ejecutar uno de los algoritmos de prueba de planaridad O (v) para probar cada inserción propuesta o grupo de inserciones?

Answer 1

Después de investigar un poco más, parece que la respuesta es "sí", hay algoritmos en línea, pero "no" no hay ninguno con O (1) tiempo de ejecución amortizado.

Aquí hay un artículo de 1999 en el Journal of the ACM, Planaridad completamente dinámica pruebas con aplicaciones , en las cuales los autores escribieron:

  

En particular, consideramos las siguientes tres operaciones en un gráfico plano G: (i) inserte un borde si el gráfico resultante permanece plano; (ii) eliminar un borde; y (iii) probar si se puede agregar un borde al gráfico sin violar la planaridad. Mostramos cómo soportar cada una de las operaciones anteriores en el tiempo O (n ^ 2/3), donde n es el número de vértices en el gráfico. El límite para las pruebas y eliminaciones es el peor de los casos, mientras que el límite para las inserciones se amortiza.

También encontré el resumen de un artículo de 1989, Incremental prueba de planaridad reclamando un O (log n) vinculado para la inserción del borde, pero no estoy seguro de si su técnica también cubre la eliminación.

El artículo de 1999 también se refiere a un algoritmo O (inverso-ackermann (total-operaciones, n)) para el caso de no eliminación, discutido en un artículo de 1992, Prueba de planaridad incremental rápida , pero CiteSeer no funciona en este momento, así que leeré el detalles más tarde.

La eliminación es útil para mi aplicación, y al tener acceso al documento de J. ACM, voy a seguir leyendo sobre la estrategia O (n ^ 2/3) amortizada.