我正在寻找以下任务的算法：
我们正在玩以下游戏：在我们面前绘制了一个平面图，例如
我们可以看到边在 3 个地方相交。我们将在不删除任何边的情况下移动顶点，以使边不再相互交叉。例如，对于给定的图，我们可以通过以下两个步骤来完成，首先移动顶点 E，
然后通过移动顶点 B
这是一个非常简单的例子。给出的平面图可能要复杂得多。
必须转换为
任何人都可以通过反复试验来做到这一点，但是在给定任何平面图结构的情况下，需要遵循的一般算法是什么。
欢迎任何形式的提示或解决方案。提前致谢！:)
问问题
1327 次
2 回答
5
如果解决方案的复杂性无关紧要，那么存在一个线性时间算法来找到每个顶点的坐标，从而使绘图是直线平面。不幸的是，它相当复杂。第一步是使用例如 Boyer--Myrvold (On the Cutting Edge: Simplified O(n) Planarity by Edge Addition, 2004) 找到一个组合平面嵌入，然后通过 Chrobak 将该组合嵌入转换为几何嵌入—— Payne（用于在网格上绘制平面图的线性时间算法，1995 年）。这些算法在 Boost Graph Library 中实现。
光谱布局是一种更简单的算法，大部分时间都可以在连接良好的图形（如您的样本）上工作。计算拉普拉斯矩阵的第二个和第三个特征向量并将它们用作 X 和 Y 坐标。
于 2014-08-26T19:42:20.287 回答
1
如果您对最低成本感兴趣，那么本文通过路径加法进行平面测试中描述的算法将找到可能的排列以生成所有可能的平面嵌入（在O(|Edges|)时间和内存中生成包含循环边缘排序的所有排列的数据结构给出一个平面嵌入以及O(|Edges|)时间和内存来为每个单独的排列生成一个嵌入）。然后，您可以遍历这些排列并找到达到的最低成本。
如果图形总是最大平面，那么这是多余的（因为只有一种可能的循环边排序），但您可能仍需要考虑许多可能的外表面。
[顺便说一句：第一个图可以在一次移动中重新排列为平面嵌入 - 将 (C) 移动到 (A) 和 (E) 之间的中点]
于 2015-03-31T11:56:27.180 回答