平面 3 連結グラフのグラフ同型のトピックについていくつかの調査を行いましたが、さまざまな制限、理論的複雑さ、および使用頻度のアルゴリズムが豊富にあり、次のように際立ったものを見つけるのに苦労しています。
さまざまなアルゴリズムを自分で理解しないと、この問題に特化した古いアルゴリズムの 1 つを使用する方がよいのか、より一般的な新しいアルゴリズムを使用する方がよいのかを知ることは困難です。考えられるすべての候補の中で、どれが最も適していますか?
Weinberg のアルゴリズムはその条件に合っていると思います。
理解しやすい:平面性テスト アルゴリズムの副産物として、G と H の回転システムを計算します。G と H は 3 結合であるため、これらの回転系は、G と H が同型である場合にのみ、時計回りと反時計回りの交換まで同型です。G でダーツ (= 方向が示されたエッジ) d を選択し、それを H のすべてのダーツ e にマッピングしてみます (H の他の向きについて繰り返します)。G は接続されているため、G の回転システムの 2 つの操作を合成することにより、d から他のすべてのダーツ d' に到達できます。対応する操作を e に適用し、同型性があるかどうかを確認します。
最大の明快さ: 平面性テストは別として、上記はコードのページです。他の誰かの平面性テストを再利用できますか? たとえば、Boostには1つあります。そうでない場合でも、naty を書き直すよりも独自に実装する方が簡単だと思います。
小さなグラフでの実用的なパフォーマンス: 平面性テストの後、Weinberg のアルゴリズムは、基本的に、ダーツごとに 2 つの同期された深さ優先トラバーサルです。総実行時間は O(|V| 2 ) で、大きな定数は潜んでいません。