問題タブ [planar-graph]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 平面グラフでの小さなサイクルの発見
私は幾何学的な無向平面グラフを持っています。これは、各ノードに位置があり、2 つのエッジが交差しないグラフであり、エッジが交差していないすべてのサイクルを見つけたいと考えています。
この問題に対する既知の適切な解決策はありますか?
私がやろうとしているのは、一種のA*ような解決策です:
- パスとして最小ヒープにすべてのエッジを挿入します
- すべてのオプションで最短経路を延長する
- 開始点以外にループバックするパスをカリングします (必要ない場合があります)。
- 指定されたエッジで ang を使用する 3 番目のパスをカリングします
誰もこれに問題があると思いますか? それは機能しますか？
c++ - グラフが平面グラフであるかどうかを確認するにはどうすればよいですか？
平面グラフとC++での色付けについて学んでいます。しかし、私はこの作業を行うためのアルゴリズムをインストールすることを知りません。誰か助けてくれませんか？
ここに私はあなたのためにいくつかの情報を持っています！これが私のコードです！そして、それはまだ機能が終了していません。誰かが「平面グラフ」とは何かを知っている場合は、以下のPlanar_Graph関数を修正してください。：Dどうもありがとう！：バツ
入力ファイルの例：
linux - 平面グラフのテストをサポートするオープンソースのグラフ描画プログラム?
グラフ理論では、平面グラフは平面に埋め込むことができるグラフです。つまり、エッジが端点でのみ交差するように平面上に描画できます。
それらには、平面グラフ テスト (つまり、特定のグラフが平面かどうかを判断する) 用に存在する多くのアルゴリズムがあります。最良のものは O(n) にあります。ここで、n は頂点の数です。
次の機能をサポートするオープン ソース プログラムはどれですか。
- 平面グラフを描画できます
- O(n) 平面グラフ テストをサポートします。
- 可変ノード サイズをサポートします。
- 固定描画境界領域をサポート
- オープンソースである
algorithm - 平面グラフ レイアウト
グラフをレイアウトする際のエッジ オーバーラップの最小化手法にはどのようなものがありますか? （できればGraphVizに関連しています）また、グラフを平面的にレイアウトできる既存のソフトウェアはありますか？
現在のレイアウト - http://www.evecakes.com/doodles/master.gif
左上隅のピンク色のセクションはきれいに見えますが、水色のセクションには回避可能なエッジ オーバーラップがあります。
hamiltonian-cycle - 立方平面グラフでハミルトニアン サイクルを見つける
比較的小さい (40 ～ 80 ノード) 立方 (3-正則) 平面グラフがあり、それらのハミルトニシティを決定する必要があります。このタスクが NP 完全であることは認識していますが、関心のあるグラフ サイズに対して非常に高速な漸近指数時間アルゴリズムを期待しています。
algorithm - 大きなランダムな平面グラフを生成する
大規模な (~ 300k 頂点) ランダム平面グラフ (ここでの「ランダム」は均一に分散されていることを意味します) を生成する最も効率的な方法は何ですか?
graph - 非平面グラフの平面化アルゴリズム
非平面グラフの平面化のための一般的なアルゴリズムはありますか?
現在、無向グラフ用の直交平面レイアウト アルゴリズムを Boost ( Boost Graph Library ) に実装することを計画しています。BGL には、無向グラフ (Boyer-Myrvold Planarity Testing) の平面性をチェックする実装があり、このメソッドによって返される平面埋め込みを使用して直交レイアウトを行う予定です。
しかし、入力グラフが非平面の場合、どうすればよいかわかりません。このようなシナリオで返された Kuratowski サブグラフを使用して、グラフを平面にする必要があります。
「非平面グラフの平面化」を Google 検索すると、複数の研究論文が返されます。どこから始めればよいかわかりません。
c# - C＃での平面埋め込み（平面面走査）アルゴリズム
グラフがありますG。グラフは平面グラフです。
グラフのすべての面を見つけたいです。平面埋め込みを作成することは、面（または領域、またはサイクル）を見つける方法であり、すべてのエッジを最大2つの面で共有する必要があることを理解しています。
C＃で平面埋め込みアルゴリズムを簡単に実装できますか？商用またはオープンソースのどちらでも構いません。
graph - n ノードの平面グラフにおける m サイクルの存在の複雑さ
G は、n 個のノードを持つ平面グラフです。
次の問題の複雑さは何ですか?
- A: G には m サイクルが含まれていますか? (m-cycle は、m 個のノード、m 個の単純なサイクルです。
- B: G のすべての m サイクルをカウントする複雑さ。
- G が任意の与えられたグラフの場合、A と B の複雑度はいくらですか?
本や紙を指すのも便利です...
algorithm - グラフ構造の直線平面埋め込み
これが私の問題です：私は平面であることがわかっている（直線のエッジを持つ）グラフ構造を持っています（つまり、エッジが交差しないところにグラフの埋め込みが存在します）。グラフを取得して、それを直線で平面に埋め込んだアルゴリズムが必要です。アルゴリズムはあまり効率的である必要はありません（O（N ^ 2）アルゴリズムで十分です）。何かアイデア/提案はありますか？