4

是否存在用于平面化非平面图的流行算法。

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

但是我不确定如果输入图是非平面的应该怎么做。我是否应该对在这种情况下返回的 Kuratowski 子图做一些事情以使图平面化。

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

4

1 回答 1

1

$K_n$ 的 $K_5$ 和 $K_{3,3}$ 子图的数量成倍增加，更不用说未成年人了，因此直接处理它们并不是非常有效。我建议翻阅上述研究论文，以了解其他人如何解决这个问题。您应该注意 (a) 提供合理解决方案和 (b) 听起来像您感兴趣的图形的属性。

于 2012-04-05T14:51:03.563 回答