Spectral partitioning works: planar graphs and finite element meshes

DOI10.1016/j.laa.2006.07.020zbMath1122.05062OpenAlexW2200304227WikidataQ105583693 ScholiaQ105583693MaRDI QIDQ869898

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

zbMATH Keywords

eigenvalue problems spectral analysis graph partitioning spectral methods graph embedding

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

Chaco

Cites Work