I have a geometric undirected planar graph, that is a graph where each node has a location and no 2 edges cross, and I want to find all cycles that have no edges crossing them.

Are there any good solutions known to this problem?

What I'm planning on doing is a sort of A* like solution:

  • insert every edge in a min heap as a path
  • extend the shortest path with every option
  • cull paths that loop back to other than there start (might not be needed)
  • cull paths that would be the third to use ang given edge

Does anyone see an issue with this? Will it even work?

algorithm language-agnostic graph-theory planar-graph
Edit
Report