平面图游戏的算法

Question

平面图游戏的算法

algorithmplanar-graph

4

我正在寻找以下任务的算法：

我们正在玩以下游戏: 在我们面前画了一个平面图，例如。 enter image description here

我们可以看到边缘在3个地方相交。我们要移动顶点，而不删除任何边，使边缘不再相互交叉。例如，对于给定的图形，我们可以通过首先移动顶点E来完成以下两个步骤， enter image description here

然后通过移动顶点B

这是一个非常简单的例子。所给的平面图可能更加复杂。 enter image description here

需要将其转换为

任何人都可以通过试错来完成它，但是在给定任何平面图结构时，需要遵循哪些通用算法。

欢迎任何提示或解决方案。提前致谢！ :)

- QED

可能是图中边交叉减少的重复问题。 - Steve Benett

@templatetypedef 确实没有一步一步的解决方案。 - Steve Benett

关于算法的问题更适合在http://programmers.stackexchange.com/上提问。在StackOverflow上，我们希望您展示您遇到问题的代码，或者询问有关编程语言或工具的具体细节。 - Dale Wilson

1

同意，这个问题应该发布在Programmers上。不幸的是它没有被发布在那里，现在已经在这里得到了回答并且被接受了。在这种情况下，交叉发布是不鼓励的。 - david.pfx

1

顺便说一句，我玩过这个游戏。疯狂节点什么的？ - david.pfx

显示剩余2条评论

2个回答

1

如果你对最低成本感兴趣，那么这篇论文描述的算法 Planarity Testing By Path Addition 将找到可能生成所有可能平面嵌入的排列（在 O(|Edges|) 的时间和内存中生成包含所有循环边排序的数据结构，以给出一个平面嵌入, 并在每个单独的排列上花费O(|Edges|) 时间和内存来生成一个嵌入）。然后您可以遍历这些排列并找到最低成本。

如果图形总是极大平面图，则这是过度的（因为只会有一个可能的循环边排序），但您仍可能需要考虑许多可能的外部面。

[作为旁注：第一张图可以通过一次移动（C）到（A）和（E）之间的中点来重新排列成平面嵌入。]

- MT0

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

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

- David Eisenstat · Accepted Answer

如果解决方案的复杂度不是问题，那么存在一种线性时间算法来找到每个顶点的坐标，使得图形是直线平面的。不幸的是，这相当复杂；第一步是使用例如Boyer-Myrvold（On the Cutting Edge: Simplified O(n) Planarity by Edge Addition, 2004）找到组合平面嵌入，然后通过Chrobak-Payne（A Linear-time Algorithm for Drawing a Planar Graph on the Grid, 1995）将此组合嵌入转换为几何嵌入。这些算法已在Boost Graph Library中实现。

一个更简单的算法，对于像您的样本这样连接良好的图表通常可以工作，spectral layout。计算Laplacian matrix的第二和第三eigenvectors，并将它们用作X和Y坐标。