這個圖嵌入可能＆它有一個名稱？

Question

我想要投影的無向圖到2D平面上，使得：

1. 的歐幾里得距離保留的分步距離（即如果A和B之間的最短路徑是除C和d之間的最短路徑短，則A和B之間的歐氏距離小於A和B之間的歐幾里德距離）

2. 的歐幾里德距離和所述階梯距離之間的最小差被最小化。理想情況下，如果沒有唯一的最小值，則生成或描述解決方案集合。

如果這是不可能的，那麼圖上的最小約束集是什麼使它成爲可能？我對這個問題一般很感興趣，儘管目前我希望它能用於有限格，並且刪除了最小值。

Answer 1

我認爲第一個要求是不可能的，至少在一般情況下是這樣。考慮一個由四個節點組成的完全連接圖，所有路徑長度都相等。在二維歐幾里得空間中選擇具有相同屬性的四個點是不可能的（除了4個重合點）。

查看Diego的一些有用信息的答案（我對圖論的知識非常有限！）。

Answer 2

它被稱爲graph embeddng。甚至有一個theorem that gives an upper limit to the distortion。我最喜歡的嵌入算法是SDE。如果您有一個SDP庫，那麼使用任何語言都可以輕鬆實現。

Here的算法有點簡單。