On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs

Benedikt Kolbe, Jack Spalding-Jamieson

In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface…