次のように、無向グラフを 2 次元平面に投影したいと考えています。
ユークリッド距離は段階的な距離を保持します (つまり、A と B の間の最短経路が C と D の間の最短経路よりも短い場合、A と B の間のユークリッド距離は A と B の間のユークリッド距離よりも小さくなります)。
ユークリッド距離とステップワイズ距離の最小差が最小化されます。理想的には、一意の最小値がない場合、ソリューションのセットが生成または記述されます。
これが不可能な場合、それを可能にするグラフの制約の最小セットは何ですか? 私は一般的に質問に興味がありますが、現時点では、最小値が削除された有限格子が必要です。
少なくとも一般的なケースでは、最初の要件は不可能だと思います。すべてのパス長が等しい、4 つのノードで構成される全結合グラフを考えてみましょう。同じ特性を示す 2D ユークリッド空間内の 4 つのポイントを選択することはできません (一致する 4 つのポイントを除く)。
役立つ情報については、ディエゴの回答を参照してください (グラフ理論に関する私の知識は非常に限られています!)。
それはグラフ埋め込みと呼ばれます。歪みに上限を与える定理さえあります。私が最も気に入っている埋め込みアルゴリズムはSDEです。SDPライブラリがあれば、どの言語でも簡単に実装できます。
これは、少し単純なアルゴリズムです。