非平面图平面化算法

Question

是否有非平面图平面化的流行算法。

我目前正计划在Boost（Boost Graph Library）中为无向图实现正交平面布局算法。 BGL有一个实现来检查无向图的平面性（Boyer-Myrvold Planarity Testing），并且我打算使用这个方法返回的平面嵌入来做一个正交布局。

但我不知道如果输入图是非平面的，应该做什么。我应该在这种情况下返回的Kuratowski子图做些什么来使图平面化。

关于“非平面图的平面化”的Google搜索返回多篇研究论文。我不知道从哪里开始。

Answer 1

$ K_ $ $有许多$ K_5 $和$ K_ {3,3} $子图，不介意未成年人，所以直接对待它们并不是非常有效。我建议翻阅这些研究论文，以便了解其他人如何解决这个问题。您应该注意以下特性：（a）给出明智的解决方案;（b）听起来像您感兴趣的图表。