最快的图形平面化算法

Question

我正在使用Processing为复杂的数据和流程开发导航系统.作为其中的一部分,我已深入了解图形布局.这一切都很有趣,我对布局算法的看法是:力导向是为了sissies(只看它的比例...哈哈),特征向量投影很酷,杉山层看起来不错但在图形图上快速失败,虽然我依赖到目前为止,在特征向量上,我需要最小化边缘交叉以真正达到数据点.我知道,我知道NP完全等

我应该补充一点,我在应用xy拳击和使用类似Sugiyama的排列来减少跨行和列的边缘交叉时取得了一些成功.即:图形(| V | = 90,平均度数log | V |)可以从11000个交叉点 - > 1500(通过盒装特征向量) - > 300通过交替行和列排列来减少交叉.

但是当地的最小值......无论它是什么都围绕着这个标记,结果并不像它那样清晰.我对灯光的研究告诉我,我真的想要使用像他们用于VLSI的平面化算法:

1. 使用BFS或其他东西制作最大平面子图1.a. 将平面子图布局很好
2. 巧妙地添加优秀边缘以恢复原始图形

请回复您对最快平面化算法的看法,欢迎您深入了解您熟悉的任何特定优化.

非常感谢!

Answer 1

鉴于所有图表都不是平面的（您知道），最好采用“次佳”方法，而不是“始终提供最佳答案”方法。

我这么说是因为我研究生的室友也遇到了和你一样的问题。他试图将图转换为平面形式，而所有保证最小边缘交叉的算法都太慢了。他最终所做的只是实现了随机算法。基本上，布置图形，然后抖动具有大量交叉的边缘的节点，最终您将处理最糟糕的边缘簇。

优点是：你可以在特定的时间后将其删除，所以如果你的时间有限，这总是会在一定的时间内出现，如果你得到一个蹩脚的图表，你可以再次运行它（超过已经布局图）以获得更好的东西，并且编码相对容易。

缺点是你并不总能在交叉处获得全局最小值，并且如果图形卡在高交叉区域，他的算法有时会将节点射到远处以尝试解决它，这有时会导致看起来非常奇怪的图形。