## 2 Graph Notions
### Minimal separation, chordal graphs, and minimal triangulation  
**Definition 2.2**:
* _A subset_ \(S\) _of vertices of a connected graph_ \(G\) _is called a separator (or sometimes a cutset) if_ \(G(V-S)\) _is not connected._
* _A separator_ \(S\) _is called an_ \(ab\)_-separator if_ \(a\) _and_ \(b\) _lie in different connected components of_ \(G(V-S)\)_, a minimal_ \(ab\)_-separator if_ \(S\) _is an_ \(ab\)_-separator and no proper subset of_ \(S\) _is an_ \(ab\)_-separator._
* _A separator_ \(S\) _is a minimal separator, if there is some pair_ \(\{a,b\}\) _such that_ \(S\) _is a minimal_ \(ab\)_-separator._  
Alternately, \(S\) is a minimal separator if and only if \(G(V-S)\) has at least 2 connected components \(C_{1}\) and \(C_{2}\) such that \(N(C_{1})=N(C_{2})=S\); such components are called _full components_ of \(S\) in \(G\). \(S\) is a minimal \(xy\)-separator for any \(\{x,y\}\) with \(x\in C_{1}\) and \(y\in C_{2}\). A connected graph with no minimal separator is a clique. When the graph is not connected, the set of minimal separators is the union of the sets of minimal separators of the connected components. **Example 2.3**: _Let us illustrate these notions on a tree: a tree has two kinds of vertices: leaves and articulation nodes (which are its minimal separators). Figure 2 shows how removing articulation node \(\{a\}\) disconnects the graph into several connected components; \(\{a\}\) is a \(df\)-separator, as \(d\) and \(f\) lie in two different components._  
**Example 2.4**: _On the more complex graph \(G\) of Figure 1: \(\{c,d,j,k\}\) is a separator, but it is not minimal. \(\{d,j,k\}\) is a minimal separator, with full components \(\{a,b,c\}\) and \(\{e,f,g\}\). \(\{j,k\}\) is also a minimal separator, with full components \(\{h,i\}\) and \(\{a,b,c,d,e,f,g\}\). Note that minimal separator \(\{j,k\}\) is included in minimal separator \(\{d,j,k\}\)._  
Note that in an arbitrary graph, there can be an exponential number of minimal separators \((O(2^{n}))\). Figure 3 shows an example of this. Figure 2: \(\{a\}\) is a \(df\)-separator. **Chordal graphs:** A graph is chordal if it has no chordless cycle of length strictly greater than 3; chordal graphs are extensions of trees and have many similar properties. [PERSON] [3] originally defined the concept of a minimal separator in order to characterize chordal graphs, by showing that a graph \(G\) is chordal if and only if every minimal separator of \(G\) is a clique. In a chordal graph, there are less than \(n\) minimal separators [4]. Figure 4 shows a chordal graph \(H\). **Perfect elimination orderings:** Another interesting characterization of chordal graphs is that they have a simplicial ordering on the vertices: a vertex is said to be _simplicial_ if its neighborhood is a clique. A graph is chordal if and only if one can repeatedly find a simplicial vertex, and remove it, until no vertex is left. Since at each step a vertex is removed, this defines a series of _transitory graphs_: at step \(i+1\), the transitory graph is input graph \(G\) from which the first \(i\) vertices have been removed. This process is called a _simplicial elimination scheme_, and defines an ordering on the vertices called a _perfect elimination ordering (peo)_. Each minimal separator of a chordal graph \(H\) is the neighborhood of a vertex in the transitory graph in the simplicial elimination scheme [4]. We will say that such a vertex _generates_ a minimal separator of \(H\) (w.r.t. a given peo of \(H\)):  
Figure 4: Chordal graph \(H\), with minimal separators: \(\{b,k\},\{c,k\},\{d,j,k\},\{j,k\},\{i,j\},\)\(\{d,g\}\). Figure 3: This graph has an exponential number of minimal separators, which are the combinations from the Cartesian product \(\{a_{1},b_{1}\}\times\{a_{2},b_{2}\}\times\ldots\times\{a_{n},b_{n}\}\). **Definition 2.5**: _Let \(H=(V,E)\) be a chordal graph, let \(\alpha\) be a perfect elimination ordering of \(H\).