次のタスクのアルゴリズムを探しています。
次のゲームをプレイしています: 目の前に描かれた平面グラフがあります。
エッジが 3 か所で交差していることがわかります。エッジが互いに交差しないように、エッジを削除せずに頂点を移動します。たとえば、与えられたグラフの場合、最初に頂点 E を移動することにより、次の 2 つの手順でそれを行うことができます。
そして、頂点 B を移動することによって
これは非常に簡単な例でした。与えられた平面グラフは、はるかに複雑になる可能性があります。
に変換する必要があります
誰でも試行錯誤でそれを行うことができますが、平面グラフ構造が与えられた場合に従う必要がある一般的なアルゴリズムは何ですか。
どんな種類のヒントや解決策も大歓迎です。前もって感謝します！:)
最小コストに関心がある場合、この論文Planarity Testing By Path Additionで説明されているアルゴリズムは、可能なすべての平面埋め込みを生成するために可能な順列を見つけます (O(|Edges|)時間とメモリ内で、循環エッジ順序付けのすべての順列を含むデータ構造を生成して、O(|Edges|)個々の順列ごとに埋め込みを生成するための平面埋め込みと時間とメモリを与えます)。次に、これらの順列を反復処理して、到達するための最低コストを見つけることができます。
グラフが常に最大平面である場合、これはやり過ぎですが (可能な循環エッジ順序は 1 つしかないため)、多くの可能な外面を考慮する必要がある場合があります。
[余談: 最初のグラフは、(C) を (A) と (E) の中間点に移動するという 1 回の移動で平面埋め込みに再配置できます]