I just read a very interesting paper by a fellow CMU roboticist -- Dave Tolliver -- titled "Multilevel Spectral Partitioning for Efficient Image Segmentation and Tracking."

http://www.cs.cmu.edu/~rcollins/Papers/tolliverwacv05.pdf

In this paper, the lattice geometry of images is exploited to define a set of coarsened graph partitioning problems. A coarse solution is propagated to increasingly finer resolutions and refined using subspace iterations. This hierarchical approach gives a 10x to 100x speedup over other Ncut methods which try to use clever sampling schemes.

If you're into spectral-based image segmentation, then check it out.