2
$\begingroup$

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

enter image description here

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you asking this for arbitrary graphs or a specific subclass (e.g. planar, triangulated, ...)? $\endgroup$
    – reinierpost
    Feb 19, 2014 at 12:45
  • $\begingroup$ 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. $\endgroup$
    – Omicron_Persei_11
    Feb 19, 2014 at 12:58
  • 2
    $\begingroup$ 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" i.imgur.com/PKdhrtN.png $\endgroup$
    – Chao Xu
    Feb 19, 2014 at 18:07
  • $\begingroup$ @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). $\endgroup$
    – Omicron_Persei_11
    Feb 19, 2014 at 18:44
  • $\begingroup$ @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... $\endgroup$
    – Omicron_Persei_11
    Feb 23, 2014 at 19:26

1 Answer 1

Reset to default
2
$\begingroup$

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"

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.