text: 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 @math -vertex graph of genus @math and maximum degree @math satisfies @math . This recovers the @math bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of @math , 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 @math whenever @math is @math -minor free. This shows, in particular, that spectral partitioning can be used to recover @math -sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on @math for graphs which exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find small separators 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 arbitrary graphs. This yields an alternate proof of the result of Alon, Seymour, and Thomas that every excluded-minor family of graphs has @math -node balanced separators.
  @cite_27: LetT be a triangulation of a quadrilateralQ, and letV be the set of vertices ofT. Then there is an essentially unique tilingZ=(Zv: v ∈ V) of a rectangleR by squares such that for every edge ofT the corresponding two squaresZ u, Zvare in contact and such that the vertices corresponding to squares at corners ofR are at the corners ofQ.
  @cite_20: The contacts graph, or nerve, of a packing, is a combinatorial graph that describes the combinatorics of the packing. LetG be the 1-skeleton of a triangulation of an open disk.G is said to be CP parabolic (resp. CP hyperbolic) if there is a locally finite disk packingP in the plane (resp. the unit disk) with contacts graphG. Several criteria for deciding whetherG is CP parabolic or CP hyperbolic are given, including a necessary and sufficient combinatorial criterion. A criterion in terms of the random walk says that if the random walk onG is recurrent, theG is CP parabolic. Conversely, ifG has bounded valence and the random walk onG is transient, thenG is CP hyperbolic. We also give a new proof thatG is either CP parabolic or CP hyperbolic, but not both. The new proof has the advantage of being applicable to packings of more general shapes. Another new result is that ifG is CP hyperbolic andD is any simply connected proper subdomain of the plane, then there is a disk packingP with contacts graphG such thatP is contained and locally finite inD.
  @cite_23: 
summary: Connections with discrete conformal mappings. One can view the minimizer of (or, more appropriately, the maximizer of the vertex version ) as a sort of global uniformizing'' metric for general graphs. In the setting of discrete conformal mappings, a number of variationally defined objects appear, and duality is often an important component in their analysis. We mention, for instance, the extremal length @cite_23 as a prominent example. It also often happens that one chooses a weight function @math as the minimizer of some convex functional, and this weight function plays the role of a discrete Riemannian metric (much as is the case in Section ); see, e.g. the work of Schramm @cite_27 and He and Schramm @cite_20 .