このグラフは埋め込み可能であり、名前を持っていますか？

Question

Iは、2D平面に無向グラフを投影するように：

1. ユークリッド距離が段階的に距離を維持（すなわち、AとBとの間の最短経路は、CとDとの間の最短パスよりも短い場合、その後、AとBとの間のユークリッド距離は、ユークリッド距離と段階的距離と最小差が最小化されるAとBとの間のユークリッド距離）

2. 未満です。理想的には、固有の最小値がない場合、解の集合が生成または記述されます。

これができない場合、可能な限り最小限に抑えるグラフの制約は何ですか？私は一般的な質問に興味がありますが、現時点では、最小限の削除をした有限格子に対して必要です。

Answer 1

少なくとも一般的なケースでは、最初の要件は不可能だと思います。すべての経路長が等しい4つのノードからなる完全に接続されたグラフを考えてみる。 2つのユークリッド空間で同じプロパティ（4つの一致点以外）を示す4つの点を選択することはできません。

いくつかの有用な情報についてはDiegoの答えをご覧ください（私のグラフ理論に関する知識は非常に限られています）。

Answer 2

graph embeddngと呼ばれています。さらにtheorem that gives an upper limit to the distortionがあります。私が一番好きな埋め込みアルゴリズムはSDEです。 SDPライブラリをお持ちの場合は、どの言語でも簡単に実装できます。

Hereさんのアルゴリズムは少しシンプルです。