## 2 Preliminaries
### Dynamic Graph Connectivity
#### 2.2.2 Edge Deletion in HDT  
We now review how HDT handles edge deletions, focusing on the aspects that are most relevant for compatibility testing and IDPP. For further details, we refer the reader to [15].  
Two cases arise when deleting an edge \(e\). If \(e\) is a non-tree edge, the graph remains connected; no further action is needed. Handling this case takes constant time. If \(e\) is a tree edge, the tree \(T\) in \(F\) containing \(e\) is split into two trees \(T_{1}\) and \(T_{2}\). Since the vertices of \(T\) may still be connected by a non-tree edge in the original graph, HDT searches for a _replacement edge_\(f\) to re-link \(T_{1}\) and \(T_{2}\). Next, we explain how a replacement edge is found.  
HDT associates with each tree or non-tree edge \(e\) an integer _level_\(\ell(e)\in\{0,\ldots,L\}\). Initially, \(\ell(e)=0\). _Promoting_\(e\) means increasing \(\ell(e)\) by one. Let \(F_{i}\) denote the sub-forest of \(F\) induced by the edges with level \(\geq i\). Thus, \(F_{L}\subseteq F_{L-1}\cdots\subseteq F_{1}\subseteq F_{0}=F\). HDT maintains the following invariants: (i) if we interpret the levels of the edges as their weights, then the edges of \(F\) constitute a maximum spanning forest of the graph; (ii) the number of nodes in any tree in \(F_{i}\) is at most \(\lfloor n/2^{i}\rfloor\), where \(n\) is the number of nodes in the graph. Thus, (a) if \(e=(u,v)\) is a non-tree edge, then \(u\) and \(v\) are connected in \(F_{\ell(e)}\), and (b) \(L\leq\lfloor\log_{2}n\rfloor\).  
Let \(e=(u,v)\) be the tree edge to be deleted. Since \(F\) was a maximum spanning forest, \(e\)'s replacement must have level at most \(\ell(e)\). We set \(i=\ell(e)\) and look for a replacement at level \(i\) as follows. Let \(T_{u}\) and \(T_{v}\) be the trees in \(F_{i}\) that contain \(u\) and \(v\), respectively. Assume \(|V(T_{u})|\leq|V(T_{v})|\). Before deleting \((u,v)\), \(T=T_{u}\cup\{(u,v)\}\cup T_{v}\) was a tree of \(F_{i}\) such that \(|V(T)|\geq 2|V(T_{u})|\). By Invariant (ii), \(|V(T)|\leq\lfloor n/2^{i}\rfloor\). Thus, \(|V(T_{u})|\leq\lfloor n/2^{i+1}\rfloor\). For each tree edge \(f\) of \(T_{u}\), we promote \(f\), making \(T_{u}\) a tree in \(F_{i+1}\). Next, we scan the level-\(i\) non-tree edges incident to \(T_{u}\) until we either find a replacement edge or all non-tree edges incident to \(T_{u}\) have been examined. If a visited edge \(f\) reconnects \(T_{u}\) and \(T_{v}\), then \(f\) is the replacement edge, and the scan stops. Otherwise, we promote \(f\). If no replacement is found at level \(i\), we decrease \(i\) by one and repeat the search. We stop if the search succeeds or \(i\) drops below zero (which means that no replacement edge exists).  
HDT maintains each forest \(F_{i}\) as a collection of ET trees. Thus, deleting an edge requires cutting it from at most \(\lfloor\log_{2}n\rfloor+1\) ET trees, and if a replacement edge is found, this edge is used to link at most \(\lfloor\log_{2}n\rfloor+1\) ET trees. The worst-case time for cutting and linking is therefore \(\mathcal{O}(\log^{2}n)\). The amortized cost of the edge scans can be shown to also be \(\mathcal{O}(\log^{2}n)\).