Spectral partitioning works: Planar graphs and finite element meshes

2006/10/03 by Daniel A. Spielman, Shang-Hua Teng, Shang‐Hua Teng · 145 citations
Computer Science · Engineering · Mathematics · #Bounded function #Chordal graph #Combinatorics #Computer science #Condition number #Discrete mathematics #Eigenvalues and eigenvectors #Finite element method #Geometry #Graph #Graph partition #Graph power #Graph theory and applications #Laplace operator #Laplacian matrix #Line graph #Mathematical analysis #Mathematics #Matrix Theory and Algorithms #Planar #Planar graph #Polygon mesh #Spectral graph theory #Upper and lower bounds #VLSI and FPGA Design Techniques

paper · pdf · doi:10.1016/j.laa.2006.07.020

published in Linear Algebra and its Applications 421(2-3), 284-305 (Elsevier BV)

openalex publication_date 2006/10/03 · crossref created 2006/10/03 · crossref issued 2007/03/01 · crossref published 2007/03/01 · crossref published-print 2007/03/01 · crossref deposited 2021/08/01 · openalex created_date 2025/10/10 · crossref indexed 2026/07/09 · openalex updated_date 2026/07/31

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]
• Eigenvalues and expanders
• A Separator Theorem for Planar Graphs
• Separators for sphere-packings and nearest neighbor graphs
• A separator theorem for graphs of bounded genus
• A separator theorem for graphs with an excluded minor and its applications
• Diameters and eigenvalues
• Spectra of graphs: theory and application
• Sphere Packings, Lattices and Groups

Cited by

• Spectral Graph Theory and its Applications
• Planar separator theorem [wikipedia]