Research on Graph Partitioning

• Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
  We design preconditioners for symmetric diagonally-dominant linear systems that enable their solution in time nearly-linear in their number of non-zero entries. Our algorithm for constructing the preconditioners makes use of two novel algorithmic tools. The first is a nearly-linear time algorithm for producing crude graph separators of nearly optimal balance. The second is a nearly-linear time algorithm for producing powerful graph sparsifiers. These have poly-logarithimc density and are 1 + \epsilon approximations of the original graph.

• Spectral Partitioning Works: planar graphs and finite element meshes
  We prove that spectral partitioning methods can be used to find good cuts of planar graphs and well-shaped meshes. Our proof relies on a new bound on the second-largest eigenvalues of the Laplacian matrices of these graphs.

• Min-Max-Boundary Domain Decomposition
  We present an algorithm for dividing well-shaped meshes into many pieces of approximately equal size such that each piece has small boundary.

• Disk Packings and Planar Separators
  We prove better bounds on the size of planar separators found by the geometric algorithm of Miller, Teng, Thurston, and Vavasis. Our analysis involves examining disk packings on the sphere.