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?