各サイクルを最大2サイクルで共有しなければならないサイクルベーシスを構築するアルゴリズム

Question

与えられたグラフ（以下に示す）が与えられた場合、サイクルベースを構築するためのアルゴリズムはありますか？ で最大で 2サイクルを共有する必要がありますか？ない単一のエッジは、その上に2つの以上のサイクルを有する

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

注

すなわち、上のグラフでは、アルゴリズムは、溶液として、私に次の5サイクルを返す必要があります。 5サイクルの他のセットは、すべてのエッジが2サイクルを超えない限り、解決策として受け入れることができます。

質問：このようなアルゴリズムはありますか？

最初にスパニングツリーを見つけて、スパニングツリー内にないエッジを追加してサイクルを完成させることができますが、サイクルベースのセットがこれを構成することは保証できません私は望む上記の機能を持っています。

また、各頂点の座標は、ではなく、となっています。

Answer 1

いくつかの検索の後で、プレーン埋め込みアルゴリズムがそのようなことを行うことができることが分かります。そのようなアルゴリズムの1つはBoyer and Myrvoldです。

このようなアルゴリズムは、ブーストライブラリのPlanar Face Traversal機能で実装されています。