9
$\begingroup$

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: example

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?

  • 0
    Yes this works, i look at your question now2012-12-04

4 Answers 4

2

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! https://stackoverflow.com/questions/4022662/find-all-chordless-cycles-in-an-undirected-graph

6

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.

  • 0
    I don't know as well!2012-12-04
3

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.

  • 1
    A bit further online research leads me to believe I'm looking for chordless cycles, would you agree? http://mathworld.wolfram.com/CycleChord.html2012-12-05
3

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