4

非平面グラフの平面化のための一般的なアルゴリズムはありますか?

現在、無向グラフ用の直交平面レイアウト アルゴリズムを Boost ( Boost Graph Library ) に実装することを計画しています。BGL には、無向グラフ (Boyer-Myrvold Planarity Testing) の平面性をチェックする実装があり、このメソッドによって返される平面埋め込みを使用して直交レイアウトを行う予定です。

しかし、入力グラフが非平面の場合、どうすればよいかわかりません。このようなシナリオで返された Kuratowski サブグラフを使用して、グラフを平面にする必要があります。

「非平面グラフの平面化」を Google 検索すると、複数の研究論文が返されます。どこから始めればよいかわかりません。

4

1 に答える 1

1

$K_n$ の $K_5$ および $K_{3,3}$ サブグラフは指数関数的に多くあり、未成年者は気にしないので、それらを直接処理するのはあまり効率的ではありません。上記の研究論文をめくって、他の人々がどのように問題に取り組んでいるかについて少し学ぶことをお勧めします. (a) 賢明な解決策を提供し、(b) 興味のあるグラフのように聞こえるプロパティに注意を払う必要があります。

于 2012-04-05T14:51:03.563 に答える