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
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You should probably specify how many nodes and links you need to deal with. $\endgroup$– Qiaochu YuanCommented Oct 20, 2009 at 16:26
-
$\begingroup$ 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? $\endgroup$– Kim MorrisonCommented Oct 20, 2009 at 17:08
-
1$\begingroup$ 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. $\endgroup$– Jason DyerCommented Oct 20, 2009 at 19:03
-
$\begingroup$ 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). $\endgroup$– streklinCommented Oct 20, 2009 at 19:04
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
3
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.
answered Oct 20, 2009 at 18:22
-
$\begingroup$ Thanks, do you have links to an existing implementation for this? $\endgroup$– GravitonCommented Oct 21, 2009 at 6:39
-
$\begingroup$ 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. $\endgroup$ Commented Oct 21, 2009 at 6:59
-
$\begingroup$ 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? $\endgroup$– GravitonCommented Oct 22, 2009 at 15:06
$\begingroup$
$\endgroup$
5
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?
-
$\begingroup$ 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. $\endgroup$ Commented Oct 20, 2009 at 17:49
-
$\begingroup$ 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. $\endgroup$– TonyKCommented Oct 20, 2009 at 18:29
-
$\begingroup$ 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. $\endgroup$ Commented Oct 20, 2009 at 18:43
-
$\begingroup$ If node 15 and 16 lie inside R4, then it should be reported as 9-8-15-16 and 15-16-13-14 $\endgroup$– GravitonCommented Oct 21, 2009 at 2:04
-
$\begingroup$ 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). $\endgroup$– TonyKCommented Oct 21, 2009 at 9:13
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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). $\endgroup$ Commented Oct 20, 2009 at 20:38
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ I mean, the cycles that travel the least number of vertex $\endgroup$– GravitonCommented Oct 22, 2009 at 15:07
-
$\begingroup$ 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! $\endgroup$– TonyKCommented Oct 22, 2009 at 15:18