<p>The solution is <a href="https://math.stackexchange.com/questions/8140/find-all-cycles-faces-in-a-graph">here</a>, I hope that it helps somebody.. The <a href="https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph">link</a> given also in the question itself contains a useful pdf from geometrictools.com</p>

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

CC BY-SA 3.0
2014-02-25T18:40:44.657Z
2014-02-25T18:40:44.657Z
2017-05-23T12:40:09.333Z
Omicron_Persei_11
<p>My initial problem is geometric, but I've reformulated it to a graph:</p>

<p><img src="https://i.sstatic.net/E1aya.png" alt="enter image description here"></p>

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

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

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

<p>I've read in <a href="http://en.wikipedia.org/wiki/Spanning_tree" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Spanning_tree</a> about fundamental cycles, but I'm not quite sure that finding the fundamental cycles will solve the problem for every case.</p>

<p>P.S.: See also this question <a href="https://stackoverflow.com/questions/13111236/how-to-detect-minimal-cycles-in-a-graph">https://stackoverflow.com/questions/13111236/how-to-detect-minimal-cycles-in-a-graph</a> - it contains mine problem formulation, but no real solution. It would really be nice to give more hints than <a href="https://www.google.com/search?q=minimal%20cycles%20in%20a%20graph" rel="nofollow noreferrer">google</a>. And <a href="https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph">https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph</a> contains some suggestions but without any serious justification.</p>

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

CC BY-SA 3.0
2014-02-19T12:45:42.520Z
Are you asking this for arbitrary graphs or a specific subclass (e.g. planar, triangulated, ...)?
reinierpost
CC BY-SA 3.0
2014-02-19T12:58:51.643Z
The graphs in question are for sure planar, bridgeless, and this is indeed a cycle cover problem. The sought collection of cycles should include each edge of the graph once of twice, but the cycles should be minimal, i.e. they should represent "Manhattan blocks".

_About crossposting_: I'm simply not sure to what forum the topic better belongs thematically, and where there are more people who know the graph theory.
Omicron_Persei_11
CC BY-SA 3.0
2014-02-19T18:07:26.340Z
I think your original problem is to find all the faces of a *planar embedding* of a graph. The new formulation might not solve your problem because a planar graph can have multiple embeddings. Should these two graphs have the same set of "minimum simple cycle" http://i.imgur.com/PKdhrtN.png
Chao Xu
CC BY-SA 3.0
2014-02-19T18:44:26.293Z
@ChaoXu This is a good remark. 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).
Omicron_Persei_11
CC BY-SA 3.0
2014-02-23T19:26:58.150Z
@ChaoXu Sorry, the problem was really to find all the faces of a planar embedding of a graph. You'd better say that there are also some special algorithms for this purpose.
But I keep the question, may be it helps someone with the same misunderstanding...
Omicron_Persei_11
<graph-theory><graph-algorithms>
minimal cycles in undirected graph
Omicron_Persei_11
# minimal cycles in undirected graph

(Asked by: username_0 on 2014-02-19)

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

![enter image description here](https://i.sstatic.net/E1aya.png)

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](https://www.google.com/search?q=minimal%20cycles%20in%20a%20graph). 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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Are you asking this for arbitrary graphs or a specific subclass (e.g. planar, triangulated, ...)?  
> **username_0**: The graphs in question are for sure planar, bridgeless, and this is indeed a cycle cover problem. The sought collection of cycles should include each edge of the graph once of twice, but the cycles should be minimal, i.e. they should represent "Manhattan blocks".  _About crossposting_: I'm simply not sure to what forum the topic better belongs thematically, and where there are more people who know the graph theory.  
> **username_2**: I think your original problem is to find all the faces of a *planar embedding* of a graph. The new formulation might not solve your problem because a planar graph can have multiple embeddings. Should these two graphs have the same set of "minimum simple cycle" http://i.imgur.com/PKdhrtN.png  
> **username_0**: @ChaoXu This is a good remark. 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).  
> **username_0**: @ChaoXu Sorry, the problem was really to find all the faces of a planar embedding of a graph. You'd better say that there are also some special algorithms for this purpose. But I keep the question, may be it helps someone with the same misunderstanding...  

---

## 1 answers

### Answer by username_0 on 2014-02-25. Score: 2 | Accepted answer

The solution is [here](https://math.stackexchange.com/questions/8140/find-all-cycles-faces-in-a-graph), I hope that it helps somebody.. The [link](https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph) 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"


---

