創建一個平面圖的對偶圖

Question

我正在試圖建立一個MSSP（多源最短路徑），但我缺乏如何構建相互轉化樹的知識，我正在尋找這個pdf。直到現在我創建了生成樹，因此創建了Plannar圖，但是因爲我不知道如何構建它的對偶。有沒有特定的算法/方法或任何可以幫助我解決這個問題的紙張？當我搜索並找不到有用的東西。

Answer 1

1. 如果你還沒有一個，你需要一個組合嵌入。有效的算法可以從關聯結構中獲得一個算法，但平面圖的自然來源通常具有自然嵌入。有很多方法來表示嵌入。我用相同的頂點逆時針順序將每個半邊的置換π映射到下一個半邊。每個（非孤立）頂點都與一個循環鏈接的輸入半邊鏈表相關聯。

2. 讓rev是將每個半邊緣映射到另一半邊緣的排列，具有相反的頭部和尾部頂點。對偶圖的嵌入置換是π的組成，其次是rev。它以順時針順序將每個半邊緣映射到臉部的下一個半邊緣（或無限臉部上的逆時針方向，因爲您正在看它的背面）。如果你親自嘗試一些例子，這會更清楚。

3. 從最初的根計算最短路徑後（我使用Dijkstra，除非MSSP實現比我的速度快得多，使用漸近更快的算法沒有太多相對改進），請執行深度優先搜索，其中屬於最短路徑樹的邊被忽略。 （另一種選擇是去參觀歐拉遊秩序的交錯樹的半邊緣，但這種做法似乎，雖然它會產生額外的對數時動態樹操作。）