厳密なグラフの埋め込みをしようとしているわけではないことに注意してください。頂点が交差することはできません)。
距離が制限された点のセットをデカルト平面にプロットできるかどうかを知るアルゴリズム的な方法を知っている人はいますか? または、さらに良いのは、点を正確に描写するために必要な最小次元数を決定する方法です。
例として: 3 つの点があり、それらがすべて互いに 1 単位離れているという制約がある場合、これを正三角形としてデカルト平面に簡単にプロットできます。
ただし、A->B = 1、A->C = 1、および B->C = 3 という制約がある場合、距離を維持しながらこれらの点をプロットすることはできません。
ただし、私の場合、3 つ以上の頂点を持つグラフがあります。グラフは間違いなく非平面です。そのようなケースの 1 つは、2 つの頂点間の「距離」を定義する重み付けされた双方向エッジによってすべてが接続されている 1407 個の頂点を含みます。
問題は、このグラフをデカルト平面上の正確な距離で描写できるかどうかを判断する方法があることです。エッジの交差せずにそれを描くことができないことは知っていますが、それをすることは気にしません。飛行機のポイントを互いに適切な距離にしたいだけです。
役立つ場合のグラフに関する追加情報:
1) 各ノードは点の集合を表します。2) エッジの重みは、ノードの各ペアからポイント セットを最適にオーバーレイし、結果のポイント セットの RMSD を取得することによって導出されます。3) 任意の 2 つのノードによって表される点のセットは、互いにペアにすることができます。つまり、各ノードは 1 ～ 8 の番号が付けられた 8 つのポイントのセットと考えることができます。この番号付けは静的です。ノード A とノード B をオーバーレイすると、A と C、B と C をオーバーレイしたときと同じ番号がポイントに付けられます。
私の考え：RMSDはR ^ 3のメトリックであるため（少なくとも私はそう信じています。この論文はそれを証明すると主張していますhttp://onlinelibrary.wiley.com/doi/10.1107/S0108767397010325/abstract）、それは私にとって可能であるはずです少なくとも R^3 でこれを行います。
ここでの私の本当の目標は、この点のセットを素敵な図形に変えることなので、3D の図形を 2D で表現できるので、実際には 3 次元の描写で十分です。また、使用している特定の最適なオーバーレイ アルゴリズムの数値的な不安定性が問題を引き起こすことも認識していますが、理想的なケースの答えに興味があります。