## 1 Introduction  
This paper is designed as a presentation for the not so well-known graph decomposition which we call \"clique minimal separator decomposition\". In view of recent applications, this decomposition is a promising tool.  
A _separator_ is a set of vertices (of a connected graph), the removal of which disconnects the graph, and a _clique_ is a set of pairwise adjacent vertices, and of course a _clique separator_ is a separator which is a clique. _Clique minimal separator decomposition_ is a process which breaks up an undirected graph into a set of subgraphs by copying the clique minimal separators into the connected components they define, as will be explained in detail further.  
Historically, clique separator decomposition was studied by graph theorists because some hard graph problems such as vertex coloring, maximum clique and testing for perfection can be solved by a Divide-and-Conquer approach by first solving them on the subgraphs defined by a clique separator decomposition, and then merging the obtained results.  
There are two main drawbacks to this decomposition:  
* First, not every graph has a clique separator.
* Second, the subgraphs obtained are not disjoint, which means that if the overlap is large, little is to be gained by a Divide-and-Conquer approach.  
However, recent research has modelized data by graphs (such as text mining data [1], biochip data [2], or any data represented by a symmetric positive matrix such as distance data). In those graphs, a clique is often an important locus, since it reflects maximum interaction between its elements. These graphs almost always have clique separators. But in any case, when these graphs are obtained by choosing a threshold in a distance matrix, one can choose a threshold which defines a graph which contains a sufficient number of clique separators.  
The fact that the subgraphs obtained overlap can be a desirable property in applications. For example, when searching for clusters of genes, it is nice to be able to allow a gene to interact with different gene groups, which is not the case with classical gene clustering.  
The theory of clique decomposition and clique minimal separator decomposition has been studied by several authors. The mathematical baggage necessary to prove the results we present here is somewhat complicated, and the results are distributed between various papers, which is one of the reasons for which this graph decomposition is not as well-known as it could be. We will describe the known results (while citing the corresponding reference papers when possible). We also devote a section to giving the proof (or at least a sketch of proof) of the main results we use.  
Our aim in this paper is to explain this decomposition as simply as possible; the basic process is not difficult to understand, and it is not difficult to implement. However, it does involve some not so easy graph notions such as minimal separation. We have organized the results so that graph theorists will find the theoretical background, and so that scientists from other areas can use and implement this decomposition, by giving examples and explaining the implementations.  
The paper is organized as follows:  
* Section 2 gives some general graph notions, some particulars on minimal separation and minimal triangulation.
* Section 3 provides a precise definition of clique minimal separator decomposition, as well as examples; we also discuss how to find the clique minimal separators of a graph efficiently, and give some properties of this decomposition.
* Section 4 gives an efficient process for computing the clique minimal separator decomposition of a graph.
* Section 5 provides a brief history of clique decomposition, with the bibliographic background as well as high-level proofs of the results we present in this paper.
* We conclude in Section 6.