Welcome to MathOverflow

Question

1

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

edited Oct 22 2009 at 15:09

asked Oct 20 2009 at 15:54

Graviton
157●8

You should probably specify how many nodes and links you need to deal with. – Qiaochu Yuan Oct 20 2009 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 2009 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 2009 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 2009 at 19:04

David Eppstein · Accepted Answer · 2009-10-20 18:22:24Z UTC

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.

Gray Taylor · Answer 2 · 2009-10-22 14:58:43Z UTC

0

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.

answered Oct 22 2009 at 14:58

Gray Taylor
450●3●10

	I mean, the cycles that travel the least number of vertex – Graviton Oct 22 2009 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 2009 at 15:18

TonyK · Answer 3 · 2009-10-21 14:12:29Z UTC

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.

Ari · Answer 4 · 2009-10-20 18:58:16Z UTC

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.

TonyK · Answer 5 · 2009-10-20 16:41:18Z UTC

2

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?

answered Oct 20 2009 at 16:41

TonyK
1,453●6●11

	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 2009 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 2009 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 2009 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 2009 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 2009 at 9:13

Algorithm to Find all the Cycle Bases in a Graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.