Spectral Partitioning Works:
Planar graphs and finite element meshes
Authors:
Daniel A. Spielman
and Shang-Hua Teng.
Bibliographic Information:
This is
UC Berkeley Technical Report number UCB CSD-96-898.
An extended abstract
appeared in Proceedings of the 37th Annual IEEE Conference
on Foundations of Computer Science, 1996.
Abstract:
Spectral partitioning methods use the Fiedler
vector---the eigenvector of the second-smallest eigenvalue of
the Laplacian matrix---to find a small separator of a graph.
These methods are important components of many scientific numerical
algorithms and have been demonstrated by experiment
to work extremely well.
In this paper, we show that spectral partitioning methods
work well on
bounded-degree
planar graphs and finite element meshes---the classes of graphs
to which they are usually applied.
While naive spectral bisection does not necessarily work,
we prove that spectral partitioning techniques
can be used to produce separators whose ratio of
vertices removed to edges cut
is $\O{\sqrt{n}}$ for bounded-degree
planar graphs and
two-dimensional meshes and $\O{n^{1/d}}$
for well-shaped $d$-dimensional meshes.
The heart of our analysis is an upper bound on the
second-smallest eigenvalues of the Laplacian matrices of these
graphs:
we prove a bound of $\O{1/n}$ for bounded-degree planar
graphs
and $\O{1/n^{2/d}}$ for well-shaped $d$-dimensional meshes.
You can download the Tech Report as
Postscript,
compressed Postscript,
PDF, or
compressed PDF.
You can download the FOCS version as
Postscript,
compressed Postscript,
PDF, or
compressed PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 13:57:34 2001