Spectral partitioning works: planar graphs and finite element meshes

DOI10.1016/J.LAA.2006.07.020zbMATH Open1122.05062OpenAlexW2200304227WikidataQ105583693 ScholiaQ105583693MaRDI QIDQ869898FDOQ869898

Authors: Daniel A. Spielman, Shang-Hua Teng 

Publication date: 9 March 2007

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2006.07.020

Recommendations

• Publication:4886053
• On the Quality of Spectral Separators
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• An efficient spectral method for bisection of regular finite element meshes

zbMATH Keywords

spectral analysiseigenvalue problemsgraph partitioningspectral methodsgraph embedding

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• A fast algorithm for particle simulations
• Eigenvalues and expanders
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Isoperimetric numbers of graphs
• Recent directions in netlist partitioning: a survey
• Title not available (Why is that?)
• On the Angle Condition in the Finite Element Method
• Title not available (Why is that?)
• ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE
• Title not available (Why is that?)
• Geometric bounds for eigenvalues of Markov chains
• A Separator Theorem for Planar Graphs
• Title not available (Why is that?)
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Provably good mesh generation
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Title not available (Why is that?)
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Title not available (Why is that?)
• Open problems of Paul Erd�s in graph theory
• Expander flows, geometric embeddings and graph partitioning
• Diameters and Eigenvalues
• Separators for sphere-packings and nearest neighbor graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Title not available (Why is that?)
• Eigenvectors of acyclic matrices
• An Algorithm for Partitioning the Nodes of a Graph
• Lower Bounds for the Partitioning of Graphs
• Direct Discretization of Planar Div-Curl Problems
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• A separator theorem for graphs of bounded genus
• Condition of finite element matrices generated from nonuniform meshes.
• Title not available (Why is that?)
• An r-Dimensional Quadratic Placement Algorithm
• A Theorem on Planar Graphs
• Title not available (Why is that?)
• Combinatorial aspects of geometric graphs
• ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
• Title not available (Why is that?)
• On Estimating the Largest Eigenvalue with the Lanczos Algorithm
• Title not available (Why is that?)
• Geometric Separators for Finite-Element Meshes
• Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
• Title not available (Why is that?)
• Separators in graphs with negative and multiple vertex weights
• Title not available (Why is that?)
• Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
• Title not available (Why is that?)
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (68)

• Data Analytics on Graphs Part I: Graphs and Spectra on Graphs
• Data Analytics on Graphs Part III: Machine Learning on Graphs, from Graph Topology to Applications
• Clustering in Hypergraphs to Minimize Average Edge Service Time
• Non-existence of annular separators in geometric graphs
• Greedy recursive spectral bisection for modularity-bound hierarchical divisive community detection
• Posterior consistency of semi-supervised regression on graphs
• An improved spectral lower bound of treewidth
• Scale fragilities in localized consensus dynamics
• Detection of core–periphery structure in networks using spectral methods and geodesic paths
• ADM-CLE Approach for Detecting Slow Variables in Continuous Time Markov Chains and Dynamic Data
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Separators in region intersection graphs
• Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity
• Title not available (Why is that?)
• The influence of Miroslav Fiedler on spectral graph theory
• Cubic polyhedral Ramanujan graphs with face size no larger than six
• A Cheeger cut for uniform hypergraphs
• On the Structure of Isometrically Embeddable Metric Spaces
• On the Fiedler value of large planar graphs (extended abstract)
• Efficient Point-to-Point Resistance Distance Queries in Large Graphs
• Eigenvalues of the Laplacian on the Goldberg-Coxeter constructions for 3- and 4-valent graphs
• Discrete uniformizing metrics on distributional limits of sphere packings
• Consistency of regularized spectral clustering
• Spectral concentration and greedy \(k\)-clustering
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Title not available (Why is that?)
• A tearing-based hybrid parallel banded linear system solver
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• An efficient spectral method for bisection of regular finite element meshes
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Spectral bisection with two eigenvectors
• Higher-order spectral clustering for geometric graphs
• Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces
• A new approach based on spectral graph theory to avoiding enclosed holes in topology optimization
• Improvements on Spectral Bisection
• A tearing-based hybrid parallel sparse linear system solver
• Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs
• On the spectral gap of a quantum graph
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Diffuse interface models on graphs for classification of high dimensional data
• Discrepancy and eigenvalues of Cayley graphs
• Metric uniformization and spectral bounds for graphs
• Community Detection and Stochastic Block Models
• The balanced connected subgraph problem for geometric intersection graphs
• Spectral trisection of finite element models
• Approximating Unique Games Using Low Diameter Graph Decomposition
• An upper bound on the algebraic connectivity of outerplanar graphs
• The geometry connectivity of hypergraphs
• An exact approach for the multi-constraint graph partitioning problem
• Title not available (Why is that?)
• A spectral lower bound for the treewidth of a graph and its consequences
• Spectral clustering and the high-dimensional stochastic blockmodel
• Spectral clustering and its use in bioinformatics
• On the Fiedler value of large planar graphs
• Network Essence: PageRank Completion and Centrality-Conforming Markov Chains
• Graph clustering
• Social order statistics models for ranking data with analysis of preferences in social networks
• Ordering trees and graphs with few cycles by algebraic connectivity
• Towards a theoretical foundation for Laplacian-based manifold methods
• On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• A note on Fiedler value of classes with sublinear separators
• The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
• Title not available (Why is that?)

Uses Software

• Chaco

This page was built for publication: Spectral partitioning works: planar graphs and finite element meshes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q869898)