# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 3 Graph Partitioning
### Multilevel Graph Partition  
A _multilevel graph partition_ is obtained by recursively partitioning a graph \(G=(V,E)\). The cells obtained in the first step are partitioned again. This process is repeated over several levels. The union of all cells obtained in every recursion step is called the set \(\mathcal{C}\) of _cells_. By definition, \(V\) is also cell. The set of cells \(\mathcal{C}\) is the multilevel graph partition. This recursive definition models closely how partition-based divide-and-conquer graph algorithms operate. However, to prove properties about multilevel partitions, we use a different, equivalent, non-recursive definition described in the next paragraph. We use this different definition in the remainder of this paper.  
A multilevel graph partition is a rooted tree \(P\) with node multiset \(\mathcal{C}\) of cells and root \(V\). Cells are subsets of \(V\). We require that, for every multilevel graph partition \(\mathcal{C}\):  
1. \(V\) is a cell, i.e., \(V\in\mathcal{C}\);
2. no cell is empty;
3. all touching cells are totally ordered by set inclusion, i.e., \(\forall C_{1},C_{2}\in\mathcal{C}:C_{1}\) touches \(C_{2}\implies C_{1}\subseteq C_{2}\lor C_{2}\subseteq C_{1}\); and
4. for all cells \(C_{1},C_{2}\in\mathcal{C}\): if \(C_{1}\subsetneq C_{2}\), \(C_{2}\) is an ancestor of \(C_{1}\), if \(C_{1}=C_{2}\), \(C_{1}\) is an ancestor of \(C_{2}\) or \(C_{2}\) is an ancestor of \(C_{1}\).  
Analogous to the tree decomposition assumption, we assume without loss of generality throughout this paper that there are at least two cells.  
We define the _children_ of a cell \(\mathcal{C}\) as the cells such that \(\mathcal{C}\) is the parent. We call a cell \(D\)_descendant_ of \(\mathcal{C}\), \(\mathcal{C}\) is on the path from \(D\) to the root. In particular, \(\mathcal{C}\) is a descendant of \(\mathcal{C}\). A cell that has no child is a _leaf_ cell.  
Finally, we introduce three terms that are only well-defined in the node-based setting. The _boundary_\(B_{\mathcal{C}}\) of a cell \(\mathcal{C}\) is the set of nodes adjacent to \(\mathcal{C}\) in \(\mathcal{G}\), i.e., \(u\in B_{\mathcal{C}}\) if there exists an edge \(\{u,v\}\) with \(u\
ot\in\mathcal{C}\) and \(v\in\mathcal{C}\). The _separator_\(S_{\mathcal{C}}\) of a cell \(\mathcal{C}\) is \(\mathcal{C}\) minus all of \(\mathcal{C}\)'s children. If \(\mathcal{C}\) has no children, then \(\mathcal{C}\)'s separator is equal to \(\mathcal{C}\), i.e., \(S_{\mathcal{C}}=\mathcal{C}\).  
Figure 4 depicts an example node-based multilevel partition of the running example. The green cell is the \(V\) cell. Its separator \(S_{V}\) is \(\{p,c\}\) and its boundary is empty. The children of \(V\) are the orange cells. Another example is the blue cell \(C_{1}=\{q,r,j,k,l\}\) in the bottom right. Its separator \(S_{C_{1}}\) is \(\{r\}\) and its boundary \(B_{C_{1}}\) is \(\{i,p\}\). It has two children, namely \(C_{2}=\{q\}\) and \(C_{3}=\{j,k,l\}\). The cell \(C_{2}\) has no children. Its separator \(S_{C_{2}}\) is therefore equal to \(\{r\}\), i.e., \(C_{2}\). The boundary of \(C_{2}\) is \(\{p,i,r\}\). Finally, the cell \(C_{3}\) has only one child, namely \(\{k,l\}\). The boundary \(B_{C_{3}}\) is \(\{i,r\}\) and the separator \(S_{C_{3}}\) is \(\{j\}\).  
Figure 3: Illustration of the touch relation. The blue and orange sets depict cells.