pequeño hallazgo ciclo en un grafo plano

Question

I tiene una geométrico no dirigido planar graph, que es una gráfica donde cada nodo tiene un lugar y no transversal 2 bordes, y que desee encontrar todos los ciclos que no tienen bordes que cruzan ellos.

¿Hay alguna buena solución conocida para este problema?

---

Lo que estoy pensando en hacer es una especie de A* como solución:

• inserto cada arista en un montón min como un camino
• extender el camino más corto con cada opción
• rutas de descarte que vuelven a iniciarse en otro lugar que no sea el inicio (podría no ser necesario)
• rutas de descarte que serían el tercero en usar un borde dado

¿Alguien ha visto un problema con esto? ¿Funcionará?

Answer 1

Mi primer instinto es utilizar un método similar a un solucionador de wall following laberinto. Esencialmente, sigue los bordes y siempre saca el borde derecho de un vértice. Cualquier ciclo que encuentre con este método será límites de una cara. Deberá hacer un seguimiento de los bordes que ha recorrido en esa dirección. Una vez que ha atravesado un borde en ambas direcciones, ha identificado las caras que separa. Una vez que todos los bordes se han recorrido en ambas direcciones, habrá identificado todas las caras por sus límites.

Answer 2

un "borde de cruce", como usted lo llama, se conoce generalmente como un chord. Por lo tanto, tu problema es encontrar todos los ciclos sin acordes.

This paper parece que puede ayudar.

Answer 3

Una manera simple de hacer esto es simplemente salir y enumerar cada cara. El principio es simple:

• Nos mantener 'a-visitado' y banderas 'visitado ß-' para cada borde, y un par de listas enlazadas doblemente de bordes no visitados para cada uno de tales bandera. La división 'α' y 'β' debe corresponder a una partición del plano en la línea correspondiente al borde en cuestión; qué lado es α y qué lado es β es arbitrario.
• Para cada vértice V:
  • Para cada par adyacente de bordes E = (V_1, V), E '= (V_2, V) (es decir, ordenar por ángulo, tomar pares adyacentes, así como primero + último):
  • Determine en qué lado se encuentra S de E (S = α o β) V_2.
  • Caminar la baldosa, a partir de V, con el lado S de E, como se describe a continuación:

Corta la baldosa se realiza por:

• Let V = V_init
• Bucle:
  • V_next = el vértice de E que no es V
  • E '= El borde adyacente a E desde V_next que está en el lado actual de E
  • S' = El lado de E 'que contiene V
  • Si V_next = V, hemos encontrado un bucle; registre todos los bordes que pasamos en el camino, y marque esos pares de bordes como visitados.
  • Si E '= E (solo hay un borde), entonces llegamos a un callejón sin salida; abortar esta caminata
  • De lo contrario, deje V = V_next, E = E ', S = S' y continúe.

espero que esto tenía sentido; tal vez necesite algunos diagramas para explicar ...