minimal cycles in undirected graph My initial problem is geometric, but I've reformulated it to a graph:



In the graph above I need to find the set of minimal simple cycles that form the whole graph. The initial problem was to separate the complex figure into the minimal closed regions. In the graph formulation I assume that is suffices to find the set of cycles that represents the whole graph with minimal number of edges in every cycle.

Every vertex is connected to at least two other vertices, i.e. there are no "hanging" vertices. The possible graphs are planar and bridgeless. However, in general the graph may contain multiple connected components (if this is a serious restriction - ignore it). The graph can be considered as both weighted and unweighted, but I think it's better to consider it as unweighted if the goal is to find the cycle basis of minimal closed regions. The graphs in question either have one planar embedding or multiple "equivalent" planar embeddings (e.g. consider the example graph: the parallel edges can be moved, but the simple closed loops will remain the same).

There is some ambiguity possible because of the parallel edges between some pairs of vertices. These multiple solutions are OK if they are equally valid.

I've read in http://en.wikipedia.org/wiki/Spanning_tree about fundamental cycles, but I'm not quite sure that finding the fundamental cycles will solve the problem for every case.

P.S.: See also this question https://stackoverflow.com/questions/13111236/how-to-detect-minimal-cycles-in-a-graph - it contains mine problem formulation, but no real solution. It would really be nice to give more hints than google. And https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph contains some suggestions but without any serious justification.

P.P.S.: Crossposting on CS.SE was removed (the question was deleted), but this question can still be moved to CS.SE if it's better fits there. Sorry for this misunderstanding.
The solution is here, I hope that it helps somebody.. The link given also in the question itself contains a useful pdf from geometrictools.com

Sorry, the question was really not that hard, but it is somehow quite popular and there's still a lot of confusion about "all faces of a planar embedding of a graph"