The mesh partitioning is motivated by the fact that the domain decomposition provides a natural route to parallelism. An automatic mesh decomposer should distribute the mesh across the individual processors so that the computational load is evenly balanced and the amount of interprocessor communication is minimized. However, the numerical experience has shown that several other issues, as the subdomain shape and connectivity, in addition to load balancing and communication costs, need to be addressed . In recent years, a considerable attention [21,33,50,69,84,87,102,134,167] has been focused on developing suitable techniques to solve the mesh partitioning problem and several powerful methods have been devised. The greedy algorithm [21,50] is based on a successive expansion of a subdomain, initially formed by one appropriately chosen element, until it comprises a sufficiently large number of elements. The expansion is usually driven by neighbourhood search schemes using the depth-first or breadth-first search. The basic disadvantage of this very fast technique resides in the fact that the final partitioning is often very far from the ``optimal'' one. However, the speed makes this technique very suitable for an initial decomposition subjected to further optimization based, for example, on the relative gain concept  or simulated annealing . The recursive bisection methods [102,159] utilize the spatial distribution of a mesh. While the coordinate recursive bisection (Cartesian, polar, or spherical) exploits only the dimensional properties of the mesh with respect to a given coordinate system, the inertial recursive bisection accounts for principal inertial properties of the mesh which are invariant with respect to the coordinate system. The spectral recursive bisection [69,84] is based on the finding that the second largest eigenvalue of the Laplacian matrix of an undirected graph associated with a mesh provides a good measure of the connectivity of the mesh and that the components of the corresponding eigenvector can be conveniently used for the mesh bisection. Although this approach provides decomposition of a high quality, computationally complexity makes its use problematic when large meshes are under consideration. This deficiency was partially eliminated by a multilevel implementation of this technique .