  Partitioning a graph into three pieces, with two of them large and connected,
and the third a small ``separator'' set, is useful for improving the
performance of a number of combinatorial algorithms. This is done using the
second eigenvector of a matrix defined solely in terms of the incidence matrix,
called the graph Laplacian. For sparse graphs, the eigenvector can be
efficiently computed using the Lanczos algorithm. This graph partitioning
algorithm is extended to provide a complete hierarchical subdivision of the
graph. The method has been implemented and numerical results obtained both for
simple test problems and for several grid graphs.
