algorithm - 具有固定节点位置的图形平面度

Question

我有一个具有固定节点位置的无向图。不能移动、合并、移除或以其他方式更改节点。边缘固定到它们的节点，但不必是直的。

我需要知道是否可以“弯曲”或“绘制”边缘以使图形是平面的（即没有边缘交叉）。

如果存在这样的算法或实现，或者您只是对如何做有想法，请告诉我！

Answer 1

“J. Pach 和 R. Wenger. Embedding plane graphs at fixed vertex locations. Graphs Combin., 17:717–728, 2001”回答了这个问题：

n 个顶点上的每个平面图都允许一个平面嵌入，该平面嵌入将每个顶点映射到预先指定的不同位置，并将每个边映射到具有 O(n) 个弯曲的多边形曲线。
这样的嵌入可以在 O(n^2) 时间内构建。

所以答案是，当且仅当图形是平面的时，您才能构建这样的图形。您可以根据wikipedia测试图形是否在 O(n) 时间内是平面的。