这个图嵌入可能吗，它有一个名字吗？

Question

我想把一个无向图投影到2d平面中，这样：

1. 欧氏距离保持逐步距离（即，如果A和B之间的最短路径短于C和D之间的最长路径，则A和B间的欧氏距离小于A和B的欧氏距离）

2. 欧氏距离和逐步距离之间的最小差被最小化。理想情况下，如果没有唯一的最小值，则生成或描述一组解决方案。

如果这是不可能的，那么图上使其成为可能的最小约束集是什么？一般来说，我对这个问题很感兴趣，尽管目前我希望它是一个去掉最小值的有限格。

Answer 1

它被称为图嵌入。甚至还有一个定理给出了畸变的上限。我最喜欢的嵌入算法是SDE。如果您有SDP库，那么在任何语言上实现都相当容易。

这里有一个更简单的算法。

Answer 2

我认为第一个要求是不可能的，至少在一般情况下是这样。考虑一个由四个节点组成的全连通图，所有路径长度相等。在二维欧几里得空间中，不可能选择四个具有相同性质的点（除了4个重合点）。

请参阅Diego的答案以获得一些有用的信息（我对图论的了解非常有限！）。