most recent 30 from http://mathoverflow.net 2013-05-23T08:09:09Z http://mathoverflow.net/feeds/question/1443 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph Graviton 2009-10-20T15:54:31Z 2009-10-22T15:09:39Z

<p>I am given a graph defined by vertexes and edges. I have to obtain all the cycle bases in a network. <strong>No coordinates will be given for the nodes.</strong></p> <p>Here's a <a href="http://deluxecourse.com/network.png" rel="nofollow">sketch</a> that illustrates my point.</p> <p><strong>Note that inside a cycle it must not contain any edge</strong></p>

http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1451#1451 TonyK 2009-10-20T16:41:18Z 2009-10-20T16:41:18Z

<p>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.<br /> 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.<br /> 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?</p>

http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1466#1466 David Eppstein 2009-10-20T18:22:24Z 2009-10-20T18:22:24Z

<p>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. <a href="http://dx.doi.org/10.1007/b99859" rel="nofollow">Kavitha et al, ICALP 2004</a>.</p>

http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1471#1471 Ari 2009-10-20T18:58:16Z 2009-10-20T18:58:16Z

<p>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.</p>

http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1656#1656 TonyK 2009-10-21T13:54:04Z 2009-10-21T14:12:29Z

<blockquote> <p>Note that inside a cycle it must not contain a link, all the cycle must be clean (no link) and closed.</p> </blockquote> <p><em>Sigh</em> 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.</p>

http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1879#1879 Gray Taylor 2009-10-22T14:58:43Z 2009-10-22T14:58:43Z

<p>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, <a href="http://research.nii.ac.jp/~uno/code/cypath.htm" rel="nofollow">this page</a> seems to describe an algorithm for enumerating such cycles.</p>