非平面图的平面化算法
是否有一种流行的非平面图平面化算法？
我目前正计划在 Boost（Boost Graph Library）中为无向图实现正交平面布局算法。 BGL 有一个实现来检查无向图的平面性（Boyer-Myrvold 平面性测试），我计划使用此方法返回的平面嵌入来进行正交布局。
但我不确定如果输入图是非平面的该怎么办。我是否应该对在这种情况下返回的 Kuratowski 子图做一些事情以使图平面化。
谷歌搜索“非平面图的平面化”会返回多篇研究论文。我不知道从哪里开始。
Is there a popular algorithm for the planarization of a non-planar graph.
I'm currently planning to implement a Orthogonal Planar Layout algorithm for undirected graphs in Boost ( Boost Graph Library ). BGL has an implementation to check the planarity of an undirected graph ( Boyer-Myrvold Planarity Testing ) and I plan to use the planar embedding returned by this method to do an orthogonal layout.
But I'm not sure what should be done if the input graph is non-planar. Should I do something with the Kuratowski sub-graph returned in such a scenario to make the graph planar.
A Google Search on "Planarization of non-planar graphs" returns multiple research papers. I'm not sure where to start.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Kn 的 K5 和 K{3,3} 子图呈指数级增长，更不用说未成年人了，所以直接对待它们是不可行的效率非常高。我建议翻阅上述研究论文，了解其他人如何解决这个问题。您应该注意以下属性：(a) 提供合理的解决方案；(b) 听起来像您感兴趣的图表。
There are exponentially many K5 and K{3,3} subgraphs of a Kn, never mind minors, so treating them directly isn't terribly efficient. I suggest flipping through said research papers to learn a bit about how other people approach the problem. You should pay attention to properties that (a) give sensible solutions and (b) sound like graphs that interest you.