A set of vertices $S\subseteq V$ is a minimal (vertex) separator of a graph $G=(V,E)$ if $G-S$ has at least two components with the property that every vertex of $S$ has a neighbour in each component.
Vertex separators and edge separators (also called cutsets) play an important role in the design of divide-conquer-algorithms, that typically can be used on all graphs. Minimal separators can be used for the design of efficient algorithms when restricted to various graph classes (with a polynomially bounded number of minimal separators) such as interval, permutation, chordal, circle and circular-arc graphs. Typically these algorithms use geometric representations of the minimal separators, so-called scanlines in a geometric intersection model.
There are various algorithmic applications of minimal separators to design efficient algorithms on special graph classes. We shall concentrate on efficient algorithms to compute the minimum fill-in and the minimum elimination tree height (also studied as vertex ranking) of graphs because of the applications of these two problems.
We shall also discuss recent progress by V. Bouchitte and I. Todinca (Lyon) concerning our so-called ESA'93 conjecture which states: ``The minimum fill-in and the treewidth of a graph can be computed by a polynomial time algorithm on each graph class having a polynomially bounded number of minimal separators.