图平面化的快速算法

Question

我正在使用处理为复杂的数据和进程开发一个导航系统。作为其中的一部分，我深入地研究了图形布局。这一切都很有趣，我对布局算法的看法是:力导向是为女人(请看它，scale...haha)，特征向量投影很酷，杉山图层看起来很好，但在图上失败得很快，虽然到目前为止我一直依赖于特征向量，但我需要最小化边缘交叉，才能真正到达数据的顶点。我知道，我知道NP-完全等。

我应该补充一点，我在应用xy装箱和使用类似Sugiyama的排列以减少行和列之间的边界交叉方面取得了一些成功。即:图(|V|=90，avg度数log_x_v_x)可以从11000次交叉-> 1500 (按盒式特征向量)通过交替行列排列-> 300来减少交叉。

但当地的极小值..。不管它是什么，都粘在这个标记上，结果并不像它可能的那样清晰。我对lit的研究表明，我真的很想使用平面化算法，就像他们在VLSI中使用的那样：

1. 使用BFS或其他方法生成最大平面子图1.a。布局平面子图nice-like
2. Cleverly添加突出的边以恢复原始图

请回答您对最快的平面化算法的想法，欢迎您深入了解您熟悉的任何特定优化。

非常感谢！

Answer 1

考虑到所有的图都不是平面图(你知道的)，最好采用“次优”方法，而不是“总是提供最佳答案”的方法。

我这么说是因为我在研究生院的室友有和你一样的问题。他试图将一个图形转换成平面图，所有保证最小边缘交叉的算法都太慢了。他所做的只是实现了一种随机算法。基本上，绘制出图形，然后有很多交叉边的跳汰机节点，最终您将处理最糟糕的边缘块。

它的优点是:你可以在特定的时间之后把它剪掉，所以如果你的时间是有限的，它总是在一定的时间内出现，如果你得到一个糟糕的图表，你可以再次运行它(在已经布置的图表之上)以获得更好的结果，而且编写代码也相对容易。

缺点是你并不总是在交叉处得到全局极小值，如果图被卡在高交叉区域，他的算法有时会将一个节点射到远处去试图解决它，这有时会导致看起来很奇怪的图形。

Answer 2

你已经知道很多图表布局，但我相信你的问题，不幸的是，还没有明确说明。

通过执行以下操作，您可以非常快地将任何图平面化：(1)在平面上随机布局图；(2)计算边交叉处的位置；(3)在交叉处创建伪顶点(这是对非平面图使用基于平面度的布局时所做的事情) (4)用新顶点和分割边扩展的图会自动平面化。

第一个困难来自于有一个算法来计算组合嵌入，以最小化边缘交叉的数目。第二个困难是使用组合嵌入在欧几里德平面上进行视觉上有吸引力的布局，例如，对于正交图布局，您可能想要最小化弯曲的数目，最大化面的大小，最小化整个图的面积，等等，这些目标可能相互冲突。