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?

Dramamine

So, what you're looking for is the boundary for each face? – Irreverence

Is this a directed or undirected graph? – Coextensive

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.

Irreverence

Good solution. The only real trick that I can see is determining "rightmost". However, since location is known then you could use the 2D analog of the cross product to test all possible exits to see which forms the smallest (counter-clockwise) angle with the current edge. – Somme

@Naaff, take all outbound angles, subtract them from the angle of edge you arrived on, mod 2*pi, take the smallest – Dramamine

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.

Kith

That sounds right, I didn't known "cord" apply outside of circles. – Dramamine

Any idea where I can download it? My university account (that has access to everything and it's dog) doesn't even seem to have access. – Dramamine

Can you get to it through ScienceDirect? dx.doi.org/10.1016/j.jda.2007.01.005 I can't find any freely-available copies. Or you could always try emailing the author and asking for a copy. If you're suitably polite, they might be happy to send you it. Or, heck, you could see if your university library gets the journal. – Kith

ScienceDirect is asking me to buy it :( and I'm not at the library right now. – Dramamine

Nowadays you can often get the papers from their authors homepages. It is the case here: math.sun.ac.za/~mwild/Marcel%20Wild%20-%20Home%20Page_files/… – Durango

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...

Coextensive

When you say "E' = The adjacent edge to E from V_next that is on the current side of E": I believe there could be multiple edges E' that satisfy this condition -- correct? Also, when you say "If V_next = V, we have found a loop", do you mean "If V_next = V_init, we have found a loop"? – Monogamist

Actually, on second thought I think this is just unknown(google)'s answer explained in a much more convoluted way - that's what I get for answering when tired :/ – Coextensive