Planaridad de fot algoritmo prueba en gráficos

Question

Estoy implementando una biblioteca gráfica y quiero incluir algunos algoritmos del gráfico básico. He leído sobre gráficos planares y decidí incluir en mi biblioteca una función que comprueba si un grafo es planar. Encontré en la web muchos algoritmos eficientes, pero todos tienen el mismo inconveniente: son muy difíciles de implementar.

Así que aquí está mi pregunta: ¿existe un algoritmo para planarity comprobar que es fácil de entender y de implementar?

Answer 1

Varios criterios para la planaridad se enumeran aquí: http://en.wikipedia.org/wiki/Planar_graph.

El Teorema de Kuratowski da un posible algoritmo, aunque es bastante lento. http://en.wikipedia.org/wiki/Planar_graph#Kuratowski.27s_and_Wagner.27s_theorems

Hopcraft y Tarjan ideado un lineales en tiempo del algoritmo. http://en.wikipedia.org/wiki/Planarity_testing#Path_addition_method

Usted puede encontrar buenas respuestas en Stack Overflow.

http://stackoverflow.com/questions/9173490/python-networkx

http://stackoverflow.com/questions/1854711/how-to-check-if-a-graph-is-a-planar-graph-or-not

Answer 2

Creo que @K. Hu sugerencia de un algoritmo basado en el teorema de Kuratowski debe ser el más fácil de entender y de aplicar. Vamos a tratar de escribirlo en pseudocódigo:

is_planar(G):
  If G is the empty graph, return TRUE.
  If G is isomorphic to K_(3,3) or K_5, return FALSE.
  For each vertex V of G:
    Let H be a copy of G with V and all adjacent edges removed.
    If not is_planar(H), return FALSE.
  For each edge E of G:
    Let H be a copy of G with E removed.
    If not is_planar(H), return FALSE.
  For each edge E of G:
    Let H be a copy of G with E contracted.
    If not is_planar(H), return FALSE.
  return TRUE.

Esto sólo suele terminar en una cantidad razonable de tiempo muy pequeños gráficos. Sin embargo, hay optimizaciones como memoization que puede mejorar el tiempo de ejecución, algo sin alterar la estructura general del programa. Posiblemente se podría extender a trabajar para las grandes gráficos de un unpathological la naturaleza, o al menos aquellos con ciertas propiedades atractivas.

Además, tiene la ventaja de generalizar fácilmente a otras superficies topológicas mientras el prohibido a los menores de edad son conocidos.