开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜