固定节点位置的图可平面性

Question

5

我有一张带有固定节点位置的无向图。节点不能被移动、合并、删除或以其他方式更改。边缘固定在它们的节点上，但不必是直线。

我需要知道是否可以“弯曲”或“绘制”边缘，使图形成为平面图（即不存在边相交）。

如果存在这样的算法或实现，或者您有关于如何完成此操作的想法，请告诉我！

- Henri

2

作为一个快速的“上限”测试，您可以简单地检查图形（忽略平面内顶点的给定位置）是否是平面图。如果不是，则您知道答案必须是“否”。如果是，则需要进一步调查。 - j_random_hacker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

这个问题的答案来自于“J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs Combin., 17:717–728, 2001”，其内容如下：

每个有n个顶点的平面图都可以映射到预先指定的不同位置，并将每条边映射为带有O(n)拐点的多边形曲线以实现平面嵌入。
这样的嵌入可以在O(n^2)时间内构建。

因此答案是，只有当图形是平面图时，您才能构建这样的图形。根据wikipedia，您可以在O(n)时间内测试一个图形是否是平面图。