2006/01/01 by Jonathan A. Kelner · 45 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Advanced Graph Theory Research #Combinatorics #Mathematics #Lemma (botany) #Bounded function #Conjecture #Embedding #Chordal graph #Pathwidth #Maximum cut #Eigenvalues and eigenvectors #Asymptotically optimal algorithm #Travelling salesman problem #Genus #Indifference graph #Discrete mathematics #Upper and lower bounds #Graph #Line graph #Algorithm #Computer science
paper · doi:10.1137/s0097539705447244
published in SIAM Journal on Computing 35(4), 882-902 (Society for Industrial and Applied Mathematics)
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/04
In this paper, we address two long-standing questions about finding good separators in graphs of bounded genus and degree: 1. It is a classical result of Gilbert, Hutchinson, and Tarjan [J. Algorithms, 5 (1984), pp. 391-407] that one can find asymptotically optimal separators on these graphs if given both the graph and an embedding of it onto a low genus surface. Does there exist a simple, efficient algorithm to find these separators, given only the graph and not the embedding? 2. In practice, spectral partitioning heuristics work extremely well on these graphs. Is there a theoretical reason why this should be the case? We resolve these two questions by showing that a simple spectral algorithm finds separators of cut ratio O(√\smash[b]g/n) and vertex bisectors of size O(√(gn)) in these graphs, both of which are optimal. As our main technical lemma, we prove an O(g/n) bound on the second smallest eigenvalue of the Laplacian of such graphs and show that this is tight, thereby resolving a conjecture of Spielman and Teng. While this lemma is essentially combinatorial in nature, its proof comes from continuous mathematics, drawing on the theory of circle packings and the geometry of compact Riemann surfaces.