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 active 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(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 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/sup 2/d/) for well-shaped d-dimensional meshes.
Keywords
Polygon meshEigenvalues and eigenvectorsPlanar graphBounded functionLaplace operatorCombinatoricsLaplacian matrixMathematicsUpper and lower boundsSpectral graph theoryPlanarGraph partitionFinite element methodCondition numberGraphComputer scienceGeometryMathematical analysisPhysicsLine graphGraph power
Affiliated Institutions
Related Publications
On the Quality of Spectral Separators
Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
Pattern vectors from algebraic graph theory
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences mus...
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
Chemical Graph Theory
INTRODUCTION. ELEMENTS OF GRAPH THEORY. The Definition of a Graph. Isomorphic Graphs and Graph Automorphism. Walks, Trails, Paths, Distances and Valencies in Graphs. Subgraphs. ...
Publication Info
- Year
- 1996
- Type
- article
- Pages
- 96-105
- Citations
- 406
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
406
OpenAlex
Cite This
Daniel A. Spielman,
Shang‐Hua Teng
(1996).
Spectral partitioning works: planar graphs and finite element meshes.
, 96-105.
https://doi.org/10.1109/sfcs.1996.548468
Identifiers
- DOI
- 10.1109/sfcs.1996.548468