[Math] Algorithm to find all the cycle bases in a graph

Question

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

Answer 1

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.