2010-08-06 83 views
4

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

我目前正計劃在Boost(Boost Graph Library)中爲無向圖實現正交平面佈局算法。 BGL有一個實現來檢查無向圖的平面性(Boyer-Myrvold Planarity Testing),並且我打算使用這個方法返回的平面嵌入來做一個正交佈局。

但我不知道如果輸入圖是非平面的,應該做什麼。我應該在這種情況下返回的Kuratowski子圖做些什麼來使圖平面化。

關於「非平面圖的平面化」的Google搜索返回多篇研究論文。我不知道從哪裏開始。

回答

1

$ K_ $ $有許多$ K_5 $和$ K_ {3,3} $子圖,不介意未成年人,所以直接對待它們並不是非常有效。我建議翻閱這些研究論文,以便了解其他人如何解決這個問題。您應該注意以下特性:(a)給出明智的解決方案;(b)聽起來像您感興趣的圖表。