最快的图平面化算法
我正在使用处理来开发复杂数据和流程的导航系统。作为其中的一部分，我非常深入地了解了图形布局。这很有趣，我对布局算法的看法是：力导向适合胆小鬼（只要看看它的比例...哈哈），特征向量投影很酷，杉山层看起来不错，但在图形图上很快失败，尽管我已经依赖到目前为止，在特征向量上，我需要最小化边缘交叉才能真正到达数据点。我知道，我知道 NP 完全等。
我应该补充一点，我通过应用 xy 拳击并使用类似 Sugiyama 的排列来减少跨行的边缘交叉并取得了一些成功列。即：图（|V|=90，平均度数log|V|）可以从11000个交叉点→> 1500（通过盒装特征向量）-> 300 通过交替行和列排列来减少交叉。
但局部极小值……无论它是什么，都停留在这个标记周围，结果并不那么清晰。我对 Lit 的研究表明，我真的很想使用平面化算法，就像他们在 VLSI 中使用的那样：
- 使用 BFS 或其他东西来制作最大平面子图 1.a.将平面子图布局得漂亮
- 巧妙地添加突出的边缘以恢复原始图
请回复您对最快平面化算法的想法，欢迎您深入了解您熟悉的任何特定优化和。
非常感谢！
I'm using Processing to develop a navigation system for complex data and processes. As part of that I have gotten into graph layout pretty deeply. It's all fun and my opinions on layout algorithms are : force-directed is for sissies (just look at it scale...haha), eigenvector projection is cool, Sugiyama layers look good but fail fast on graphy graphs, and although I have relied on eigenvectors thus far, I need to minimize edge crossings to really get to the point of the data. I know, I know NP-complete etc.
I should add that I have some good success from applying xy boxing and using Sugiyama-like permutation to reduce edge crossings across rows and columns. Viz: graph (|V|=90,avg degree log|V|) can go from 11000 crossings -> 1500 (by boxed eigenvectors) -> 300 by alternating row and column permutations to reduce crossings.
But the local minima... whatever it is sticks around this mark, and the result is not as clear as it could be. My research into the lit suggests to me that I really want to use the planarization algorithm like what they do use for VLSI:
- Use BFS or something to make the maximal planar subgraph
1.a. Layout the planar subgraph nice-like - Cleverly add outstanding edges to recover the original graph
Please reply with your thoughts on the fastest planarization algorithm, you are welcome to go into some depth about any specific optimizations you have had familiarity with.
Thanks so much!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
鉴于所有图表都不是平面的（您知道），最好采用“次佳”方法，而不是“始终提供最佳答案”方法。
我这么说是因为我研究生的室友也遇到了和你一样的问题。他试图将图转换为平面形式，而所有保证最小边缘交叉的算法都太慢了。他最终所做的只是实现了随机算法。基本上，布置图形，然后抖动具有大量交叉的边缘的节点，最终您将处理最糟糕的边缘簇。
优点是：你可以在特定的时间后将其删除，所以如果你的时间有限，这总是会在一定的时间内出现，如果你得到一个蹩脚的图表，你可以再次运行它（超过已经布局图）以获得更好的东西，并且编码相对容易。
缺点是你并不总能在交叉处获得全局最小值，并且如果图形卡在高交叉区域，他的算法有时会将节点射到远处以尝试解决它，这有时会导致看起来非常奇怪的图形。
Given that all graphs are not planar (which you know), it might be better to go for a "next-best" approach rather than a "always provides best answer" approach.
I say this because my roommate in grad school had the same problem you did. He was trying to convert a graph to planar form and all the algorithms that guarantee minimum edge crossings were too slow. What he ended up doing what just implementing a randomized algorithm. Basically, lay out the graph, then jigger nodes that have edges with lots of crossings, and eventually you'll handle the worst clumps of edges.
The advantages were: you can cut it out after a specific amount of time, so if you're time limited this always comes in under a certain amount of time, if you get a crappy graph you can just run it again (over the already laid out graph) to get something better, and it's relatively easy to code up.
Disadvantage is you don't always get the global minima in crossings, and if the graph gets stuck in high crossing areas, his algorithm would sometimes shoot a node way off into the distance to try and resolve it, which sometimes causes really weird looking graphs.
您已经知道很多图形布局，但不幸的是，我相信您的问题仍然没有明确说明。
您可以通过执行以下操作快速平面化任何图形：(1) 在平面上随机布局图形 (2) 计算边交叉的位置 (3) 在交叉处创建伪顶点（这就是无论如何，当您对非平面图形使用基于平面性的布局时，您都会这样做）（4）用新顶点和分割边扩展的图形自动是平面的。
第一个困难来自于计算组合嵌入的算法，以最小化边缘交叉的数量。第二个困难是使用组合嵌入在欧几里得平面中进行视觉上有吸引力的布局，例如，对于正交图形布局，您可能希望最小化弯曲数量，最大化面的大小，最小化整个图形的面积，等等，并且这些目标可能会相互冲突。
You know already lots of graph layout but I believe your question is still, unfortunately, underspecified.
You can planarize any graph really quickly by doing the following: (1) randomly layout the graph on a plane (2) calculate where edges cross (3) create pseudo-vertices at the crossings (this is what you anyway do when you use planarity based layout for non-planar graphs) (4) the graph extended with the new vertices and split edges is automatically planar.
The first difficulty comes from having an algorithm that calculates a combinatorial embedding that minimizes the number of edge crossings. The second difficulty is using that combinatorial embedding to do layout in Euclidean plane that is visually appealing, e.g. for orthogonal graph layout you might want to minimize the number of bends, maximize the size of faces, minimize the area of the graph as a whole, etc., and these goals might conflict each other.