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 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?
Best Answer
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 ?
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.