### Eigenvalue bounds, spectral partitioning, and metrical deformations via flowsEigenvalue bounds, spectral partitioning, and metrical deformations via flows

Access Restriction
Subscribed

 Author Biswal, Punyashloka ♦ Lee, James R. ♦ Rao, Satish Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Metric embeddings ♦ Network flows ♦ Spectral graph theory Abstract We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every $\textit{n}-vertex$ graph of genus $\textit{g}$ and maximum degree $\textit{D}$ satisfies $λ_{2}(G)=O((g+1)^{3}D/n).$ This recovers the $\textit{O}(\textit{D}/\textit{n})$ bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of $\textit{O}((\textit{g}+1)poly(\textit{D})/\textit{n}),$ but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that $λ_{2}(G)$ = $O(Dh^{6}log$ $\textit{h}/\textit{n})$ whenever $\textit{G}$ is $K_{h}-minor$ free. This shows, in particular, that spectral partitioning can be used to recover $\textit{O}(&sqrt;\textit{n})-sized$ separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on $λ_{2}$ for graphs that exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find separators of sublinear size in a general class of geometric graphs. Moreover, while the standard “sweep” algorithm applied to the second eigenvector may fail to find good quotient cuts in graphs of unbounded degree, our approach produces a vector that works for $\textit{arbitrary}$ graphs. This yields an alternate proof of the well-known nonplanar separator theorem of Alon, Seymour, and Thomas that states that every excluded-minor family of graphs has $\textit{O}(&sqrt;\textit{n})-node$ balanced separators. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 3 Page Count 23 Starting Page 1 Ending Page 23

#### Open content in new tab

Source: ACM Digital Library