動態平面圖邊雙連通性簡介

02-05

這個部分是冬令營交流里最後的一部分內容，也是最難的一部分，我覺得看懂這演算法對我來說還是有點困難所以先放點簡介吧……我還是太菜了 T T

本文尚在施工中，可能會更新

原文：J. Hershberger, M. Rauch, and S. Suri, Fully dynamic 2-edge-connectivity in planar graphs

Topology Tree

看完論文以後才對 Topology Tree 的用途有了一點進一步的認識。之前覺得這個複雜度根號，寫起來很麻煩還要處理度數才能用的數據結構到底是拿來幹什麼的。這個做法里發揮了很多 Topology Tree 的其他很多數據結構難以企及的地方，比如說：

我們可以在 $O(log n)$ 的時間內把 Topology Tree 在某個節點處 $u$ 展開，展開意味著用一些 Topology Tree 中（互不相交）的 cluster 來代表整棵樹（每個 cluster 看成一個點），且這些 cluster 中必須有一個只包含 $u$ 的 cluster 。通過把 Topology Tree 在 $u,v$ 展開我們可以得到一個點數 $O(log n)$ 的新圖（cluster graph），只要我們能把 cluster graph 的信息（每個 cluster 內部， cluster 之間連邊）處理出來，那麼我們就可以在 cluster graph 上進行一般圖可以進行的操作（複雜的修改/詢問）了。

在之前看的 Topology Tree 里少提了一點，我們可以要求度數為 3 的 cluster 中只能包含一個點，複雜度不會改變。這就意味著每個 cluster 至多有兩個邊界節點 $v_1,v_2$ ，從而穿過這個 cluster 的路徑就唯一（即 $path(v_1,v_2)$ ），因此我們可以維護這個路徑的相關信息。

基於這些想法，我們來介紹如何用 Topology Tree 維護平面圖邊雙連通性。我們的出發點和之前一致，通過維護生成樹中哪些樹邊被非樹邊覆蓋了來維護雙連通性。

以下用小寫字母代表樹上的節點，大寫字母代表 Topology Tree 中的 cluster 節點，如果我們用小寫字母（比如 $u,v$ 等）指代了 Topology Tree 中的某個節點，那就是樹上的節點在 Topology Tree 上對應的只包含了它（比如 $u,v$ ）的 cluster 節點。

本文中 cluster 和塊是等價的。

Coverage Graph

如前所述，我們可以對於每個度數不超過 2 的 cluster 維護有關 $path(v_1,v_2)$ 的信息。我們考慮從所有塊內出發到塊外的邊，則這條邊會對 Topology Tree 中 $u$ 到 $v$ 的路徑上的所有塊產生影響。然而在一個塊內我們無法記錄所有 $(u,v)$ ，因為有的 $v$ 可能並沒有在 cluster graph 上出現，這樣會破壞複雜度。但我們發現在 $u$ 所在的塊我們並不關心 $v$ 到底是誰，我們可以只用 $mathrm{lca}(u,v)$ 來描述它所指向的目標（方向）。由於對於一個塊 $C$ 而言 LCA 只有 $O(log n)$ 種，考慮把 LCA 相同的邊分為一類。

由於我們並不知道 $path(u,v)$ 在離開 $C$ 的時候到底是從 $v_1$ 出去的還是從 $v_2$ 出去的，我們還是不知道到底有哪些邊被覆蓋了。不過這些不重要，因為到了 cluster graph 里我們自然就知道這些了。我們考慮所有 LCA 相同的邊的 $u$ 到 $path(v_1,v_2)$ 上的投影，令其中最左邊的點和最右邊的點分別為 $l,r$ ，我們可以發現如果最後從 $v_1$ 出去被覆蓋的路徑就是 $path(v_1,r)$ ，否則就是 $path(l,v_2)$ 。於是我們可以把 $path(l,r)$ 縮成一個點（無論如何都會被覆蓋）。縮點後的 $path(v_1,v_2)$ 稱作 coverage graph 。用鏈表維護所有縮起來的點，對於每個縮起來的點維護和它相關的所有種類的邊（縮點左側的邊和右側的邊分別用一個鏈表）。

Edge Bundles

我們用它們指向的 cluster 和這類邊的數量來表示一類邊，稱其為 Edge Bundle 。如之前所述目標設定為 $mathrm{lca}(u,v)$ ，稱為 LCA targeting 。為了處理修改和詢問我們需要把 LCA targeting 改成 precise targeting （即目標直接設定為 $v$ 所在的 cluster ，由於是在修改和詢問時 cluster graph 中 $v$ 所在的 cluster 是唯一確定的）。因此我們需要在兩種模式之間切換。

從 precise targeting 向 LCA targeting 切換是顯然的。對於反向的切換，由於 cluster graph 也是平面的，我們對這棵樹做一遍順時針的歐拉遍歷，所有非樹邊形成了一個其上形如 (((...))) 的括弧序列，因此我們可以掃一遍來確定哪些 edge bundle 是同一條邊。

Calculating the coverage graphs

為了計算塊 $C$ 的 coverage graph 我們先計算兒子的再把它們的合併起來，有以下幾種情況：

$C$ 只有一個兒子：什麼都不用做
$C$ 有兩個度數為 3 和 1 的兒子： $C$ 的度數為 2 ，然而由於度數為 3 和度數為 1 都只有一個點所以直接把度數為 1 的 coverage graph 拿來就好了。
$C$ 有兩個度數為 1 的兒子： $C$ 為根，兩個兒子的 coverage graph 里也只剩一個 edge bundle 了刪了就行了
$C$ 有兩個度數為 2 和 1 的兒子：和下一種差不多但少了那種麻煩的情況，一起說
$C$ 有兩個度數為 2 的兒子：令 $A$ 和 $B$ 是 $C$ 的兒子，我們需要把連接 $A,B$ 的 edge bundle 刪掉，至多有三個 edge bundle ：在 $path(v_1,v_2)$ 左側右側可能有兩個，繞過整個生成樹一周可能會有一個。在左側右側的 edge bundle 可以通過鏈表的兩端來找到，另外一種如何找到之後會提到。在刪除 edge bundle 的時候我們把 $path(v_1,v_2)$ 上對應的部分縮起來。如果有相鄰的 edge bundle 有相同的目標也需要縮在一起（可以證明如果兩個 edge bundle 有相同的目標且不相鄰，那麼必然是繞過整個生成樹一周的邊）。

由於我們無法在所有點都存儲一份它自己的 coverage graph ，我們在合併過程中記錄合併的過程（稱為 recipe），在展開 Topology Tree 需要它兒子的 coverage graph 的時候再撤回即可。

Modification

由於詢問是在 cluster graph 上暴力詢問一遍就不多說了（由於 cluster graph 是平面的所以點邊都是 $O(log n)$ 的），主要說修改。

幾種修改其實都大同小異，先說怎麼保證度數為 3 。我們把一個點表示成一個長度為其度數的環，每個環上的點度數為 2 剩下的一個度數用於連出邊。注意連的時候不要破壞原圖的平面性。

加入邊：展開 $u,v$ ，在 cluster graph 里加上這條邊
刪除非樹邊：展開 $u,v$ ，在 cluster graph 里刪去這條邊
刪除樹邊：展開 $u,v$ ，暴力找到一個連接 $u,v$ 兩個連通塊的 edge bundle ，繼續 expand 下去直到我們確定這條用於替換的非樹邊，用這條非樹邊替換要刪的邊，然後把要刪的邊刪掉

進行這些步驟以後剩下的部分都是公共的：在已知修改的情況下更新 Topology Tree 。

首先我們確定修改後新樹的結構（但是暫時不對樹作出修改），把所有受到影響的 cluster 展開，然後我們切換到 precise targeting 並以此計算新的 LCA targeting ，接下來我們計算受影響的點的 recipe 。由於 LCA 改變，邊的 LCA targeting 受到影響，因此一些種類邊的 $l,r$ 可能會發生改變。由於受影響的邊只有 $O(log n)$ 條，涉及到需要重建的節點有 $O(log^2 n)$ 個，我們把它們也展開，從底向頂每次合併兩個塊，建出新樹。

關於合併在計算 coverage graph 的時候我們已經提到過了，但還有一種特殊情況要處理。我們維護每種深度的 edge bundle 有哪些。指向深度為合併後節點的深度的那個 edge bundle 必然就是我們所求的特殊邊（事實上 $(u,v)$ 本來就該在 $mathrm{lca}(u,v)$ 處被刪掉）。之後我們暴力把這條邊對應路徑上的點縮起來。均攤複雜度是 $O(log^2 n)$ 的。