Graph partitioning is a fundamental combinatorial optimization problem that has many practical applications such as in supporting efficient load balancing for parallel processing, in VLSI layout, and in data clustering. This proposed research program focuses on the study of spectral methods for graph partitioning. Spectral methods make use of the eigenvectors of graph matrices (e.g., the Laplacian or the adjacency matrix of a graph) to construct a quality partitioning. They have been popularly used in practice for partitioning meshes in scientific simulation, for dividing graphs derived from circuits, and for clustering data in web-graph analysis and information organization. However, the quality of the partition that these methods should produce has so far eluded precise analysis. Spielman and the PI made some breakthrough progresses. In particular, by proving that the second smallest eigenvalue of the Laplacian matrices of bounded-degree planar graphs is at most O(1/n), Spielman and the PI showed that proper use of spectral techniques can produce a bisection of graphs with cut size at most $O(sqrt{n})$, which is best possible for the family of planar graphs.
