Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Intro: I'm working on a real-world engineering problem that can be translated to an undirected graph. I'm an aerospace engineer, so perhaps I don't know/use the correct mathematical terms to describe my problem, sorry for that :)

Problem: In this graph I need to detect all 'smallest cycles', i.e. all cycles that do not contain other cycles. My application is not time-critical, or more specifically the graph's I'll load in are small (<1000 nodes with ~4 edges per node), and they are analyzed only once, so processing time is not a real issue. I have two questions.

1 - On cycle detection

I have found already how to detect all cycles in a graph, by doing a DFS to find the cycle base for the graph, from which all other cycles may be found by XOR-ing the incidence vectors.

In this picture I start with graph 1. I want my algorithm to finally return subgraphs (cycles) 2 & 3, but not 4.

Here's a picture, I'm not allowed to post it as an image yet due to me being a new user :( https://www.dropbox.com/s/xwwpve2j1tncwy4/graph_question.jpg

If that link doesn't work: http://s9.postimage.org/6o0idbt27/graph_question.jpg

I think I essentially need a way to detect if a node is contained in a region described by a cycle, e.g. that the 'center node' in my drawing is contained in cycle 4 any tips?

Edit: I'm looking for Circuits apparently, which I found out thanks to Hans Engler's answer!

2 - Bonus: edge intersections

In the models I'll analyze it is unlikely but possible that edge intersections exist. I just realized that while typing the above, and I have no clue yet if this poses a problem for decomposing the graph into cycles. Does it?

share|improve this question
    
I am sorry to tell you, but i can not open the link you posted. Edit: Ok, so i looked at your question and i hope i understand. My answer: Why dont you use if statements to check if the cycles touch each other or the coordinates of one cycle are between the other one? Edit2: Ok, best answer is picked, i think i have nothing to do here anymore. flies away –  Christoph Escore Samer Dec 4 '12 at 13:54
    
I 've added a second link, does that one work? –  Jelle Veraa Dec 4 '12 at 14:01
    
If graph is planar then use Euler formula: en.wikipedia.org/wiki/Planar_graph –  unknown Dec 4 '12 at 14:01
    
Ah, I had spotted that one and thought 'hmmm, that sounds interesting', but my lack of mathematical knowledge failed me - i couldn't see that was the solution. For my second question: what happens if the graph is non-planar? –  Jelle Veraa Dec 4 '12 at 14:07
    
Yes this works, i look at your question now –  Christoph Escore Samer Dec 4 '12 at 14:10
show 1 more comment

4 Answers

up vote 1 down vote accepted

Minimal cycles (those that contain no cycles as strict subsets) are called circuits.

Itai and Rodeh gave an algorithm in 1977 that finds a circuit of minimal size.

Boros et alii in 2006 gave a general algorithm that finds (enumerates) all circuits with up to $k$ nodes in incremental polynomial time, for a more general situation (in matroids). The degree of the polynomial depends on $k$. So the task of finding all circuits of size $\le k = 10$ for a graph with $n = 1000$ nodes may be computationally infeasible. I think there are exceptions for certain type of graphs, perhaps planar ones.

share|improve this answer
    
Thanks, that helps better than the previous answer :) Many of the nodes in my problem are likely to be part of easy-to-detect leafs, so my problem might be feasible. –  Jelle Veraa Dec 4 '12 at 16:33
1  
A bit further online research leads me to believe I'm looking for chordless cycles, would you agree? mathworld.wolfram.com/CycleChord.html –  Jelle Veraa Dec 5 '12 at 13:27
add comment

The term smallest cycle is not defined well. Informally, graphs are used when we only care about the the relations between vertices (whether there are edges or not) only. Look at the graphs that I posted. For you, are these graphs different ?enter image description here

In the left graph, imagine rotating the points 5,6 around the imaginary line joining vertices 2,4 180 degrees. Now we get the graph on the right. In fact, these two graphs are isomorphic. Now in the right graph I guess you would select the cycle 12643 and leave 12543. In the right graph, you would do the opposite . But the two graphs are really the same.

Thus, your definition of shortest cycles is not a graph property since two isomorphic graphs may not satisfy it together.

Note: If you do not consider the right and left objects the same, then it is not possible to treat them as graphs for your application. Maybe you will need to talk about the coordinates of the vertices.

share|improve this answer
    
Thanks, I think you pinpointed the part of graphs I didn't get :) I was looking at them in a sense of maps, where nodes have fixed positions + edges, in stead of only edges. Would yo know of a way to describe my problem so that i can detect what I want to detect? –  Jelle Veraa Dec 4 '12 at 14:16
    
I think you will need to talk about the coordinates of the vertices. –  Amr Dec 4 '12 at 14:18
    
I see you edit now: for my application both are the same, I only care for cycles as defined in graph theory, the location of the nodes on this cycle are less relevant. –  Jelle Veraa Dec 4 '12 at 14:18
    
So you consider the left and right graphs the same ? –  Amr Dec 4 '12 at 14:19
    
Essentially yes (or at least, it doens't represent my problem yet fully, but I think it provides a workable basis) –  Jelle Veraa Dec 4 '12 at 14:22
show 4 more comments

I think the problem is a bit incorrectly specified. And amr is completely right..

You could get a criterion like this:

For a particular cycle there are no other shorter(less edges) cycles on its subset of vertices. (If this is true, that particular cycle is "simple")

Check in you array of result circles, which ones comprise the shorter ones and delete them.

However, that won't deal with the described problem of isomorphism and you would get 3 subgraphs from amr's picture

share|improve this answer
add comment

Now that I finally have the correct terms to look for, I found my exact problem on Stack Overflow, with a solution posted as well. Thanks all for your responses! http://stackoverflow.com/questions/4022662/find-all-chordless-cycles-in-an-undirected-graph

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.