Algorithm to Construct Cycle Basis, with the Condition that Each Edge Must be Shared by At Most 2 Cycles
Given a graph ( shown below), is there an algorithm that allows me to construct a cycle basis, with the condition that each edge must be shared by at most 2 cycles?
That is, for the above graph, the algorithm should return me the following 5 cycles as the solution:
C1=>e1,e2,e13,e3
C2=>e13,e4,e5
C3=>e5,e9,e6
C4=>e7,e6,e10,e8
C5=>e10,e9,e12,e11
Note that not a single edge has more than 2 cycles on it. Any other set of 5 cycles-- as long as 开发者_Python百科all the edges don't have more than 2 cycles on it-- can be accepted as solution.
Question: Is there such an algorithm?
I can construct a set of cycle basis by first finding spanning tree, and then complete the cycles by adding edges that are not inside the spanning tree, but I can't guarantee that the the set of cycle basis constructed this way has the above feature I desired.
Also, the coordinates of each vertex are not known.
After some searching, it turns out that plane embedding algorithm can do such things. One of such algorithm is Boyer and Myrvold.
Such an algorithm is implemented in Planar Face Traversal function in boost library.
精彩评论