Daniel A. Spielman and Shang-Hua Teng

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-96-898

, 1996

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/CSD-96-898.pdf

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 <i>O</i>(sqrt[<i>n</i>]) for bounded-degree planar graphs and two-dimensional meshes and <i>O</i>(<i>n</i>^1/<i>d</i>) for well-shaped <i>d</i>-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs.

---

BibTeX citation:

@techreport{Spielman:CSD-96-898,
    Author= {Spielman, Daniel A. and Teng, Shang-Hua},
    Title= {Spectral Partitioning Works: Planar Graphs and Finite Element Meshes},
    Year= {1996},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5359.html},
    Number= {UCB/CSD-96-898},
    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 <i>O</i>(sqrt[<i>n</i>]) for bounded-degree planar graphs and two-dimensional meshes and <i>O</i>(<i>n</i>^1/<i>d</i>) for well-shaped <i>d</i>-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs.},
}

EndNote citation:

%0 Report
%A Spielman, Daniel A. 
%A Teng, Shang-Hua 
%T Spectral Partitioning Works: Planar Graphs and Finite Element Meshes
%I EECS Department, University of California, Berkeley
%D 1996
%@ UCB/CSD-96-898
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5359.html
%F Spielman:CSD-96-898