Thumbnail
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

   Open content in new tab
Source: ACM Digital Library