問題タブ [planar-graph]

平面埋め込みを計算するアルゴリズムを実装しようとしています。

一連のグラフ ( rome graphs ) に対して実行し、結果を別の実装 (yfiles) の結果と比較することで、結果の検証を開始しました。ただし、特定の平面グラフにはさまざまな埋め込みが存在する可能性があるため、平面/非平面の答えが等しいかどうかのみを確認できます。

計算した埋め込み (隣接リストでの順序付け) が正しい平面埋め込みであることを確認するにはどうすればよいですか?

おそらく間違った埋め込みを取得するいくつかのケースをすでに発見しました。失敗したグラフの場合、通常、埋め込みを手動で描画するのは困難です。任意のグラフを指定すると、グラフの平面図を作成できるというブースト ドキュメントの状態がわかりました。これにより、グラフが平面であり、平面性の証明書が簡単に確認できることが証明されます。しかし、順序付けられた隣接リストだけから、絶対確実なアルゴリズムの方法でそのような図面を作成できるかどうか、またはどのように作成できるかもわかりません。

（ところで、ここに私のコードがあります）

有向平面グラフがあります。したがって、平面埋め込みを行うことができます。ノード s と t が必要で、特定の埋め込みに従って s と t の間の左端のパスを見つけたいと思います。

左は、コメントで説明されているデビッドと定義されています。つまり、「左」は無限面と時計回り/反時計回りの規則に関して定義されます。パス p は、サイクル p*rev(q) が他の面と同様に無限面の巻き上げに関して少なくとも反時計回りである場合、同じ端点を持つパス q の左側にあります。

そんなことがあるものか？パスが別のパスから離れているかどうかをプログラムに伝える方法がわかりません。私はいくつかの論文を読みましたが、それを実装する方法を説明していませんでした。誰かがアイデアを持っていますか？

彼の顔のリストがある場合、平面グラフを描画するアルゴリズムはありますか?

パスの追加や頂点の追加など、平面性をテストして平面埋め込みを生成する複雑なアルゴリズムがいくつかあることは知っていますが、それは私が探しているものではありません。

パズル : 平面上の一般的な位置に偶数の点がある場合 (つまり、3 つの点が同一線上にない場合)、点をペアに分割し、各ペアの 2 つの点を 1 本の直線で接続して、直線が行が重なっていませんか？

私の解決策：1つの簡単なアプローチ（単純すぎるようです）。

一番左の x 座標の点から始めて、次に左端の x 座標まで線を引きます。次に、次に小さいポイントのペアを見つけて接続します。

これは正しいです？

現在、最小全域木のトピックを学んでおり、ほとんど理解していますが、まだ理解していないことがいくつかあります。無向加重グラフを扱っています。

まず、MST を見つけるには O(E*log V) のコストがかかることを知っています。ここで、平面グラフを扱うときに、線形時間 - O(V+E) に最適化したいと考えています。

次に、単位正方形の n 個の点の例を見て、O(sqrt n) の重みを持つ MST が存在することを示すことに成功しました。問題は、この MST を見つけるアルゴリズムが見つからなかったことです。

ありがとう、または

次のタスクのアルゴリズムを探しています。

次のゲームをプレイしています: 目の前に描かれた平面グラフがあります。

エッジが 3 か所で交差していることがわかります。エッジが互いに交差しないように、エッジを削除せずに頂点を移動します。たとえば、与えられたグラフの場合、最初に頂点 E を移動することにより、次の 2 つの手順でそれを行うことができます。

そして、頂点 B を移動することによって

これは非常に簡単な例でした。与えられた平面グラフは、はるかに複雑になる可能性があります。

に変換する必要があります

誰でも試行錯誤でそれを行うことができますが、平面グラフ構造が与えられた場合に従う必要がある一般的なアルゴリズムは何ですか。

どんな種類のヒントや解決策も大歓迎です。前もって感謝します！:)

ブースト グラフ ライブラリには、最大平面グラフ用に平面埋め込みアルゴリズムが実装されているようです。また、非平面グラフを平坦化するために実装されているものはありますか? うまくいけば、交差を最小限に抑える何か。

Open Graph Drawing Frameworkにはいくつかの平面化コードがあることがわかりましたが、ブーストで何かがあればそれを使用したいと思います。

この前の質問は同様のことを尋ねていますが、boost でのそのようなアルゴリズムの存在について直接ではありません。