An algorithm for constructing the basis of a cycle with the condition that each edge should be divided into no more than 2 cycles

Question

Given the graph (shown below), is there an algorithm that allows me to build a cycle basis with the condition that each edge should be divided by no more than 2 cycles?

That is, for the above graph, the algorithm should return the following 5 cycles to me as a solution:

C1=>e1,e2,e13,e3 C2=>e13,e4,e5 C3=>e5,e9,e6 C4=>e7,e6,e10,e8 C5=>e10,e9,e12,e11 

Please note that on one edge no more than two cycles. Any other set of 5 cycles - until all edges have more than two cycles on it, can be taken as a solution.

Question: Is there such an algorithm?

I can build a loop basis set by first finding a spanning tree, and then fill the loops by adding edges that are not inside the spanning tree, but I cannot guarantee that the loop basis set constructed in this way is higher, I wanted.

In addition, the coordinates of each vertex are not known.

Answer 1

After some searching, it turns out that such an attachment algorithm can do such things. One such algorithm is Boyer and Myrvold .

Such an algorithm is implemented in the Planar Face Traversal function in the boost library.