Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am given a graph defined by vertexes and edges. I have to obtain all the cycle bases in a network. No coordinates will be given for the nodes.

Here's a sketch that illustrates my point.

Note that inside a cycle it must not contain any edge

share|improve this question
    
You should probably specify how many nodes and links you need to deal with. –  Qiaochu Yuan Oct 20 '09 at 16:26
    
Please at least capitalise your question in a sensible way. I'm tempted to suggest closing this question as ill-posed. Further, I'm pretty comfortable with closing questions simply on the basis of the asker not having bothered to learn the standard terminology ... Opinions? –  Scott Morrison Oct 20 '09 at 17:08
1  
I feel reticent about outright closing questions just on the basis of improper terminology because often the reason why they haven't been able to find the answer in the first place is they are unaware of what words to search for. Sometimes these people aren't irresponsible, just running into the problem from a different discipline. –  Jason Dyer Oct 20 '09 at 19:03
    
I don't know how good an idea that is - there is I think a gray area where the poster may not be entirely familiar with subject as they just began looking into it (or have trouble with english). Now if the lack of terminology makes the question unclear, or make no sense then sure close it. However I figure if the question is clear but the terminology isn't spot on, I don't see a reason why an answer can't be provided and maybe the correct terminology pointed out. (All assuming the question would have been appropriate here in the first place of course). –  streklin Oct 20 '09 at 19:04
add comment

5 Answers

up vote 11 down vote accepted

Maybe what you want is a cycle basis? That is, a set of cycles such that any other cycle can be found by adding and subtracting combinations of cycles in the basis. One can find a cycle basis easily for any graph by finding a spanning tree and then, for each edge that's not in the tree, reporting the cycle formed by that edge together with the tree path connecting its endpoints. In a plane-embedded graph, the set of interior faces forms a cycle basis, matching what the sketch describes. Finding the shortest cycle basis is more complicated but still known in polynomial time; see e.g. Kavitha et al, ICALP 2004.

share|improve this answer
    
Thanks, do you have links to an existing implementation for this? –  Graviton Oct 21 '09 at 6:39
    
Finding a spanning tree should be implemented in any computational graph theory package (which is included with or can be added onto any general program like Mathematica, Maple, SAGE, etc.) and I suspect that finding a cycle basis is implemented in most as well. –  Harrison Brown Oct 21 '09 at 6:59
    
David, let's say if I don't know the coordinates of the vertexes, how can I "report the cycle formed by that edge together with the tree path connecting its endpoints" for the non-spanning-tree edge? –  Graviton Oct 22 '09 at 15:06
add comment

According to your sketch, you don't want cycles that enclose more than one face Ri. For instance, you are not interested in the cycle 9-8-14-16-15-13, because it contains two faces, R4 and R5.
But if this is the case, your problem is ill-posed. If I don't have the coordinates of the nodes, then for all I know, nodes 15 and 16 could lie on the other side of L14, inside R4. And in this case, I would want to include the cycle 9-8-14-16-15-13.
So you have to decide: do you give me the coordinates? Or do you want every cycle in the graph, including for instance 2-10-9-8-14-16-15-13-12-11?

share|improve this answer
    
I'm not sure if you don't need coordinates or a particular planar embedding. The cycle 9-8-14-16-15-13 could be eliminated on the basis that its "diagonal" 13-14 is also an edge. –  Michael Lugo Oct 20 '09 at 17:49
    
Where does your "diagonal" criterion come from? Not from the OP! And if you try to make it precise, I suspect that it will turn out to be unworkable. –  TonyK Oct 20 '09 at 18:29
    
It's not what the OP said but it looks like what the OP wants. Even in this case it's a bit tricky, though; my criterion would identify the "outer face" of the graph as a face. –  Michael Lugo Oct 20 '09 at 18:43
    
If node 15 and 16 lie inside R4, then it should be reported as 9-8-15-16 and 15-16-13-14 –  Graviton Oct 21 '09 at 2:04
    
But Ngu, 9-8-15-16 can't be a cycle. There is no link from 8 to 15 (or 8 to 16, if 9-8-16-15 is what you meant). –  TonyK Oct 21 '09 at 9:13
add comment

It seems like the OP is looking for a list of faces and their boundaries for a planar graph. However, without coordinates or an embedding in the plane, this is definitely ill-posed. As a simple counterexample, consider the complete graph K4. This has 4 possible faces (123,124,134,234), but any embedding in the plane has only 3 of them. This leads to 4 different possible answers, for the same graph, depending on which vertex is placed in the center of the other three. This means that, without more information, the problem doesn't have a unique answer.

share|improve this answer
    
If the planar graph is 3-connected, though, the faces are exactly the nonseparating cycles, so they can be defined graph-theoretically without respect to an embedding (and the definition makes some sense for nonplanar graphs as well). –  David Eppstein Oct 20 '09 at 20:38
add comment

Note that inside a cycle it must not contain a link, all the cycle must be clean (no link) and closed.

Sigh This edit doesn't help the situation at all. What does 'inside' mean, if your graph doesn't come with an embedding in the plane? How do I know whether nodes 15 and 16 lie 'inside' R4, if I don't have their coordinates? Look at Ari's answer for more enlightenment.

share|improve this answer
add comment

By 'clean cycle' do you perhaps mean 'chordless cycle'? This I think is well-defined without an embedding, as it's just a condition on adjacency of vertices. If so, this page seems to describe an algorithm for enumerating such cycles.

share|improve this answer
    
I mean, the cycles that travel the least number of vertex –  Graviton Oct 22 '09 at 15:07
    
If you were right, Wntrmute, then the perimeter would count as a cycle in OP's example, which presumably is not desired. On the other hand, it's impossible to know what OP really wants, as all attempts to elicit this information have so far met with a blank stare and a meaninngless 'clarification', as here. I think we've done enough! –  TonyK Oct 22 '09 at 15:18
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.