多面圖（平面3連通圖）同構算法？

我已經在平面3連通圖的圖同構的話題上進行了一些研究，但是有不同的限制，理論複雜性和使用頻率的算法豐富，我很難找到一個突出的如：多面圖（平面3連通圖）同構算法？

很難知道不了解不同的算法本身，無論我對這個問題還是更老的更專業的算法之一，或者更新，更通用的算法，我都會更好。 在所有可能的候選人中，哪一個最適合？

希望這會好一點。您可能會考慮標記遷移到我們其他網站之一。我不確定這會在這裏得到多大的牽引力。 – Will 2012-03-15 11:44:13

我很欣賞這種擔憂。在發佈我的問題之前，我覺得這可能不是最好的SE，但我不能提出更合適的問題 - 在我看來，這不是理論上的計算機科學，它不是一個關於軟件開發的概念性問題，也不是真的數學等...你能建議你認爲哪個網站最適合？ – 2012-03-15 13:29:00

你的猜測和我一樣好。我只對三大（和程序員）非常熟悉，因爲那是我最主要處理的...... – Will 2012-03-15 14:08:23

我認爲溫伯格算法符合法案。

易於理解：計算G和H的rotation systems作爲平面度測試算法的副產品。由於G和H是3連通的，所以這些旋轉系統是同構的，直到當且僅當G和H是同構的時候順時針和逆時針互換。在G中選擇一個dart（=具有指示方向的邊）d並嘗試將其映射到H中的所有darts（並重復其他H方向）。由於G是連通的，因此可以通過組合G的旋轉系統的兩個運算從d到達所有其他的飛鏢d'。將相應的運算應用於e並檢查是否存在同構。
最大淨度：除平面度測試外，以上是一頁代碼。也許你可以重用別人的平面度測試？例如，Boost中有一個。如果沒有，我仍然認爲實現你自己比重寫nauty更容易。
小圖的良好實際性能：在平面度測試之後，Weinberg算法基本上是針對每個飛鏢的兩次同步深度優先遍歷。總運行時間爲O（| V | ），沒有潛伏的大常量。

2012-03-17 20:13:03

注意：Hopcroft和Tarjan的| V | log | V |算法比較簡單;我現在無法訪問他們的文章。另一方面，線性時間平面性測試和二次時間平面性測試之間的差異是一些奇特的數據結構，所以如果您自己編寫測試，那麼您也可以在那裏解決二次時間問題。 – 2012-03-17 20:22:21

回答