問題タブ [planar-graph]

いくつかの頂点とそれらの間に定義されたいくつかのエッジで構成される 2D 平面に接続グラフがあります。グラフの全体的な形状は必ずしも凸であるとは限りません。つまり、凸包の隣接する頂点が常にエッジで接続されているわけではありません。このグラフの「輪郭」を見つける既存のアルゴリズムはありますか? 私を最も悩ませている問題は、このアウトライン ポリゴンに、元のグラフの頂点ではなく、2 つのエッジの交点である頂点が含まれている可能性があることです。そのため、対処方法がよくわかりません...

ありがとう！

ニコ

ここで具体的な質問。各頂点が別の頂点への接続数を指定し、次のルール/プロパティが適用されるグラフがあるとします。

1- グラフは不完全になる可能性があります (すべての頂点が互いに接続している必要はありません)。

2- 2 つの頂点が反対方向にある場合にのみ、それらの間に 2 つの接続が存在する可能性があります(例: A は B を指し、B は A を指します)。

3-それらが2D平面上にあると仮定すると、接続の交差はありません（接線でさえありません）。

4-プロパティを尊重し、ソリューションが一意かどうかを知るだけで、最短経路には関心がありません。

5-可能な解決策はありません

編集：具体的でなくて申し訳ありません。ここで私のポイントを明確にしようとします: 私がやりたいことは、いくつかの頂点が与えられ、グラフが接続されているかどうかを知ることです (すべてのポイントが少なくともグラフに接続されている場合)。与えられた頂点はそれのグラフを作成することが不可能な場合があるので、解決策があるかどうか、解決策が一意であるかどうか、または (最悪の場合のシナリオ) 可能な解決策がないかどうかを知りたいです。ポイント4と5を明確にすると思います。グラフには方向がなく、接続は曲線ではなく、直線のみです。ノード（頂点）は固定されており、W / E入力からの位置があります。私は最善のアプローチを知りたいと思っていました.私は研究してきました. 以上です、お返事遅くなってすみません

EDIT2 :各頂点が平面行列の行と列にあり、同じ列または行の他の頂点とのみ接続できると考えると、問題は異なりますか? つまり、90/180/270/360 のストレート接続になります。これは可能性を大幅に縮めますよね？

n ノードのセットが 2 つあります。ここで、あるセットの各ノードを別のセットの別のノードに接続したいと考えています。結果のグラフには交差がないはずです。

私はいくつかのスイープ ライン アルゴリズムを知っています (交差が発生する場所を確認するための Bentley-Ottmann-Algorithmですが、これらの交差を解決するためのアルゴリズムは、ブルート フォース アプローチを除いて見つかりませんでした。

1 つのセットの各ノードは、他のセット内の任意のノードに接続できます。

この問題を解決する (効率的な) アルゴリズムへのポインターはありますか? 実装は必要ありません。

EDIT1：

の問題に対する 1 つの解決策を次に示しますn=7。

黒い点はノードのセットで、赤い点はセットです。黒の各ノードは、それらを結ぶ線が交差しないように、1 つの赤のノードに接続する必要があります。

EDIT2：

さらに明確にするために：すべてのノードの位置は固定されており、結果のグラフにはn個のエッジがあります。また、解決策が存在するという証拠もありませんが、解決策がない例を作成できませんでした。このような平面グラフの作成が常に可能であるという証拠がどこかにあると確信しています。また、考えられるすべてのソリューションではなく、 1 つのソリューションのみが必要です。

仕事

重複していない (しかし接触している) 多角形のセットから双対グラフを計算します。

例

ポリゴンA、B、およびC、それらの部分的に共有された座標 1 ～ 22 (黄色) および双対グラフ (青色)。

データ

ポリゴンのセットSがあります。すべてのポリゴンP _iは、座標の順序付きリストとして表されます。ポリゴンP _iのエッジa_b は、 P _{i,(a,b) で}表されます。

考え

多角形は面を表し、したがって双対グラフのノードを表します。ポリゴンP _iの隣接する面を識別するには、P _iのすべてのエッジを他のすべてのポリゴンP _jのすべてのエッジと比較します。エッジが他の多角形と共有されている場合、P _iとP _jは隣接しています。

これにより、後で削除できる大量の複数のエッジが作成されます。

問題

このアルゴリズムは、 O(E ² )で実行されるため、あまり効率的ではありません。ここで、Eは多角形のセットSのエッジの数を示します。

改善案

最初のステップでエッジ インデックスを作成します。これにより、実行時間がO(2×E) = O(E)に短縮されます

次数 2 のすべてのノードを削除します (これはデュアル グラフには影響しないと思いますか?)

質問

• 私は正しい軌道に乗っていますか？
• このタスクに対して承認されたアルゴリズムはありますか?

Rでネットワークグラフが平面かどうかをテストする方法はありますか? 私はigraphを見ましたが、役に立ちませんでした。

BGLツールボックスを使用してMATLABでできることは知っていますが、Rで試した人がいるかどうか知りたい.

平面性チェック アルゴリズム (例: LR 平面性、PC ツリー、PQ ツリーなど) を拡張して、タイプに応じて一部のエッジを交差させることができるかどうかを理解しようとしています。

A、B、Cの3つの異なるタイプのエッジを持つグラフがあります

タイプ A のエッジは、他のエッジと交差できません。

タイプ B のエッジはタイプ C のエッジと交差でき、その逆も可能です。

簡単な LR 平面性テストを既に見ましたが、この機能をうまく実装できませんでした。

既存のアルゴリズムを使用してこれらのルールで調整することは可能ですか、それともこれをサポートするアルゴリズムが既に存在しますか?