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.

Answer 2

A "crossing edge", as you call it, is generally known as a chord. Thus, your problem is to find all chordless cycles.

This paper looks like it may help.

Answer 3

A simple way to do this is to simply go out and enumerate each face. The principle is simple:

• We maintain 'α-visited' and 'β-visited' flags for each edge, and a pair of doubly-linked lists of unvisited edges for each such flag. The 'α' and 'β' division should correspond to a partition of the plane on the line corresponding to the edge in question; which side is α and which side is β is arbitrary.
• For each vertex V:
  • For each adjacent pair of edges E = (V_1, V), E'=(V_2, V) (ie, sort by angle, take adjacent pairs, as well as first+last):
  • Determine which side S of E (S=α or β) V_2 lies on.
  • Walk the tile, starting at V, using side S of E, as described below:

Walking the tile is performed by:

• Let V = V_init
• Loop:
  • V_next = the vertex of E that is not V
  • E' = The adjacent edge to E from V_next that is on the current side of E
  • S' = The side of E' that contains V
  • If V_next = V, we have found a loop; record all the edges we passed by on the way, and mark those edge-pairs as visited.
  • If E' = E (there is only one edge), then we have hit a dead end; abort this walk
  • Otherwise, let V = V_next, E = E', S = S' and continue.

I hope this made sense; it perhaps needs some diagrams to explain...