I am facing the following problem, let $G(V, E)$ be an unweighted planar graph, find all the minimal cycles of $G$.
[UPDATE 1] A minimal cycle $c$ of $G$ is a cycle in $G$ such that there is no edge between two nodes of $c$ outside of $c$. For example, consider the graph below:
[UPDATE 1]
[UPDATE 1] The cycles [1, 2, 5, 6], and [2, 3, 4, 5] are minimal cycles, while the cycle [1, 2, 3, 4, 5, 6] is not, since there exist an edge between the nodes 2 e 3 outside of the cycle [1, 2, 3, 4, 5, 6].
I know that this problem has already been discussed a lot throughout the internet, however, I have not found a valid solution so far. Firstly, I will dive into the solutions I have tried and seen, so you will understand what I mean by "not found a valid solution". And secondly, I will show some possible thoughts I, and possibly the reader, have had concerning this problem.
Historical Notes:
So, follows a list sorted chronologically:
- Algorithm to find all the cycle bases in a graph (link):
[UPDATE 1] A Cycle Basis, or bases as the thread title states although I never heard of using this word for this purpose, is a minimal set of cycles $C$ that allows every Eulerian subgraph, a subgraph that admits an Eulerian cycle, in $G$ to be expressed as a symmetric difference of basis cycles of $C$. Let's take a look at the unweighted graph example below:
[UPDATE 1]
[UPDATE 1] A Cycle Basis would be $C = \{c_1 = [1, 2, 6, 5], c_2 = [2, 3, 4, 5, 6]\}$. Since the Eulerian subgraphs of the depicted example can be expressed as symmetric difference of the cycles in $C$, $c_1 \Delta \emptyset = c_1$, $c_2 \Delta \emptyset = c_2$, and $c_1 \Delta c_2 = [1, 2, 3, 4, 5]$.
In that thread, the asker asks for the same problem I am facing, however, the answer checked as valid by the asker, actually does not solve the problem, since the answer only focuses on finding a cycle basis, not necessarily composed of minimal cycles. Although the answerer even cites a related paper (A Faster Algorithm for Minimum Cycle Basis of Graphs - Kavitha et al., ICALP 2004), unfortunately, this will not work.
[UPDATE 1] A Minimum Cycle Basis is a cycle basis in which the sum of the weights of the cycles is minimum. The Cycle Basis $C = \{c_1 = [1, 2, 6, 5], c_2 = [2, 3, 4, 5, 6]\}$ already is a Minimum Cycle Basis for the previous presented example, if we consider the graph as unweighted. While the Cycle Basis composed by the cycles [1, 2, 3, 4, 5], and [6, 2, 3, 4, 5], which has 10 of weight, is not a Minimum Cycle Basis.
In this same thread, there is a bunch of comments based on the assumption that obtaining the faces set of a planar embedding, in case the graph is planar, of the graph would solve the problem. That is, the set of All Faces of a planar embedding of a graph is equivalent to the set of All Minimal Cycles of this same graph. However, this not necessarily is true. Let's take a look at the planar graph below:
and at a planar embedding of this same graph:
Note that although the faces [3, 4, 6], [1, 7, 8, 3, 2], [15, 17, 19, 18], [13, 16, 17, 15, 14], [18, 19, 21, 20], [9, 11, 12, 13, 14], and [1, 2, 4, 5] are minimal cycles, the faces [2, 3, 6, 4], [1, 5, 4, 3, 8, 10, 9, 7], [7, 9, 14, 15, 18, 20, 10, 8], and [9, 10, 20, 21, 19, 17, 16, 13, 12, 11] are not. In order to exist an equivalence between the set of All Faces of a planar embedding of a graph and the set of All Minimal Cycles of this same graph, it is necessary that the chosen planar embedding reflects the minimal cycles as its faces if such planar embedding exists.
- For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles (link) and Minimal cycles in undirected graph (link):
Both threads rely on the same point as discussed in the previous thread.
- Algorithm for finding minimal cycles in a graph (link):
[UPDATE 1] Same problem I am facing. However, the presented answer does not suffice, since a Minimal Cycle Basis, which is the same as Cycle Basis since every Cycle Basis already is minimal, not necessarily will be the set of All Minimal Cycles, just take a look at the Cycle Basis example of the second picture.
Possible thoughts:
- Find the edges of each polygon (cycle):
Considering the nodes' coordinates availability, and that the input graph is planar. One may think "Well, why don't we find the edges that compose each polygon (cycle)?", and the answer to this question is "That's is trivial when the polygon is convex, indeed there is a solution given at the thread". However, for the case where the polygon is not convex, I need to be honest, I do not know how to proceed. Case anyone has anything to contribute concerning this, I would like to hear.
- Backtracking algorithm:
Design an exponential time complexity algorithm to find all possible cycles of the graph and select only those minimal. Yes, it would work, however, it would be very time-consuming, given I am working with graphs with $|V|$ ~ 1000.
- Polynomial algorithm:
A good strategy would be to propose a polynomial solution, if possible, for this problem. But, I just have no idea how to come up with it, or if it is even possible.
Well, that is all have tried regarding this problem. And, I would like to know if anyone has any feedback for me, I would really appreciate it. If anyone detected any error or has any questions, please let me know.
Very thank you for your time and consideration, and best regards.
[UPDATE 1] Recommendations made by @Misha Lavrov.