Spectral Graph Partitioning
What do eigenvalues and eigenvectors (of Laplacian matrices) reveal about graphs? Can we use them to find good cuts? In this talk, we'll see a result of Spielman-Teng that explains why spectral partitioning techniques perform well in practice. Keywords -- spectral methods, Laplacian matrix, Fiedler vector, planar graphs, Koebe-Andreev-Thurston embedding.