algorithm - small cycle finding in a planar graph

Question

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?

Answer 1

My first instinct is to use a method similar to a wall following maze solver. Essentially, follow edges, and always take the rightmost edge out of a vertex. Any cycles you encounter with this method will be boundaries of a face. You'll have to keep track of which edges you've traversed in which direction. Once you've traversed an edge in both directions, you've identified the faces it separates. Once all edges have been traversed in both directions, you'll have identified all faces by their boundaries.