# Spectral partitioning works planar graphs and finite element meshes

Spectral Partitioning Works: Planar graphs and nite element meshes

Preliminary Draft

Daniel A. Spielman Shang-Hua Tengy February 13, 1996

Abstract

Spectral partitioning methods use the Fiedler vector|the eigenvector of the secondsmallest eigenvalue of the Laplacian matrix|to nd a small separator of a graph. These methods are important components of many scienti c numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and nite element meshes| the classes of graphs to which they are usually applied. While naive spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce p separators whose ratio of vertices removed to edges cut is O ( n) for bounded-degree planar graphs and two-dimensional meshes and O n1=d for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs.

1. Introduction

Spectral partitioning has become one of the most successful heuristics for partitioning graphs and matrices. It is used in many scienti c numerical applications, such as mapping nite element calculations on parallel machines Sim91, Wil90], solving sparse linear systems PSW92], and partitioning for domain decomposition CR87, CS93]. It is also used in VLSI circuit design and simulation CSZ93, HK92, AK95]. Substantial experimental work has demonstrated that spectral methods nd good partitions of the graphs and matrices that arise in many applications BS92, HL92, HL93, PSL90, Sim91, Wil90]. However, the quality of the partition that

Computer Science Division, U.C. Berkeley, CA 94720, spielman@cs.berkeley.edu. Supported in part by an NSF postdoc. After July 1996, Department of Mathematics, M.I.T. y Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, steng@cs.umn.edu. Supported in part by an NSF CAREER award (CCR-9502540) and an Intel research grant. Part of the work was done while visiting Xerox PARC.

1

these methods should produce has so far eluded precise analysis. In this paper, we will prove that spectral partitioning methods give good separators for the graphs to which they are usually applied. The size of the separator produced by spectral methods can be related to the Fiedler value|the second smallest eigenvalue of the Laplacian|of the adjacency structure to which they are applied. By showing that well-shaped meshes in d dimensions have Fiedler value at most O 1=n2=d , we show that spectral methods can be used to nd bisectors of these graphs of size at most O n1?1=d . While a small Fiedler value does not immediately imply that there is a cut along the Fiedler vector that is a balanced separator, it does mean that there is a cut whose ratio of vertices separated to edges cut is O n1=d . By removing the vertices separated by this cut, computing a Fiedler vector of the new graph, and iterating as necessary, one can nd a bisector of O n1?1=d edges. In particular, we prove that bounded-degree planar graphs have Fiedler value at most O (1=n), which implies that p spectral techniques can be used to nd bisectors of size at most O ( n) in these graphs. These bounds are the best possible for well-shaped meshes and planar graphs. The spectral method of graph partitioning was born in the works of Donath and Ho man DH72, DH73] who rst suggested using the eigenvectors of adjacency matrices of graphs to nd partitions. Fiedler Fie73, Fie75a, Fie75b] associated the second-smallest eigenvalue of the Laplacian of a graph with its connectivity and suggested partitioning by splitting vertices according to their value in the corresponding eigenvector. Thus, we call this eigenvalue the Fiedler value and a corresponding vector a Fiedler vector. A few years later, Barnes and Ho man Bar82, BH84] used linear programming in combination with an examination of the eigenvectors of the adjacency matrix of a graph. In a similar vein, Boppana Bop87] analyzed eigenvector techniques in conjunction with convex programming. However, the use of linear and convex programming made these techniques impractical for most applications. By recognizing a relation between the Fiedler value and the Cheeger constant Che70] of continuous manifolds, Alon Alo86] and Sinclair and Jerrum SJ89] demonstrated that if the Fiedler value of a graph is small, then directly partitioning the graph according to the values of vertices in the eigenvector will produce a cut with a good ratio of cut edges to separated vertices (see also AM85, Fil91, DS91, Mih89, Moh89]). Around the same time, improvements in algorithms for approximately computing eigenvectors, such as the Lanczos algorithm, made the computation of eigenvectors practical PSS82, Sim91]. In the next few years, a wealth of experimental work demonstrated that spectral partitioning methods work well on graphs that usually arise in practice BS92, HL92, PSL90, Sim91, Wil90]. Spectral partitioning became a standard tool for mesh partitioning in many areas HL93]. Still, researchers were unable to prove that spectral partitioning techniques would work well on the graphs encountered in practice. This failure is partially explained by results of Guattery and Miller GM95] demonstrating that naive applications of spectral partitioning, such as spectral bisection, will fail miserably on some graphs that could conceivably arise in practice. By bounding the Fiedler values of the graphs of interest in scienti c applications|bounded-degree planar graphs and well-shaped meshes|we are able to show that 2

1.1. History

spectral partitioning methods will successfully nd good partitions of these graphs. In a related line of research, algorithms were developed along with proofs that they will always nd small separators in various families of graphs. The seminal work in this area was that of Lipton and Tarjan LT79], who constructed a linear-time algorithm that produces a 1=3-separator p of 8n nodes in any n-node planar graph. Their result improved a theorem of Ungar Ung51] which demonstrated that every planar graph has a separator of size O (pn log n). Gilbert, Hutchinson, and Tarjan GHT84] extended these results to show that every graph of genus at most g has a separator of size O pgn . Another generalization was obtained by Alon, Seymour, and Thomas AST90], p who showed that graphs that do not have an h-clique minor have separators of O(h3=2 n) nodes. Plotkin, Rao, and Smith PRS94] reduced the dependency on h from h3=2 to h. Using geometric techniques, Miller, Teng, Thurston, and Vavasis MT90, MTTV96a, MTTV96b, MTV91, MV91, Ten91] extended the planar separator theorem to graphs embedded in higher dimensions and showed that every well-shaped mesh in Rd has a 1=(d+2)-separator of size O(n1?1=d). Using multicommodity ow, Leighton and Rao LR88] designed a partitioning method guaranteed to return a cut whose ratio of cut size to vertices separated is within logarithmic factors of optimal. While spectral methods have been favored in practice, they lacked a proof of e ectiveness. In Section 2, we introduce the concept of a graph partition, review some facts from linear algebra that we require, and describe the class of spectral partitioning methods. In Section 3, we prove the embedding lemma, which relates the quality of geometric embeddings of a graph with its Fiedler value. We then show (using the main result of Section 4) that every planar graph has a \nice" embedding as a collection of spherical caps on the surface of a unit sphere in three dimensions. By applying the embedding lemma to this embedding, we prove that the Fiedler value of every bounded-degree planar graph is O(1=n). In Section 4, we show that, for almost every arrangement of spherical caps on the unit sphere in Rd, there is a sphere-preserving map that transforms the caps so that the center of the sphere is the centroid of their centers. It is this fact that enables us to nd nice embeddings of planar graphs. In Sections 5 and 6, we extend our spectral planar separator theorem to the class of overlap graphs of k-ply neighborhood systems embedded in any xed dimension. This extension enables us to show that the spectral method nds cuts of ratio O(1=n1=d ) for k-nearest neighbor graphs and well-shaped nite element meshes. In Section 7, we present an elementary proof that from any vector perpendicular to the all-ones vector with small Rayleigh quotient, one can obtain a cut of small ratio. In Section 8, we extend the results of Guattery and Miller to show that our results are essentially the best possible given current characterizations of well-shaped meshes. We present natural families of graphs for which Fiedler vectors can be used to nd cuts of good ratio, but not good balance. We discuss why these graphs exist and why they might not appear in practice.

1.2. Outline of paper

3

2. Introduction to Spectral Partitioning

In this section, we de ne the spectral partitioning method and introduce the terminology that we will use throughout the paper.

2.1. Graph Partitioning

Throughout this paper, G = (V; E ) will be a connected, undirected graph on n vertices. A partition of a graph G is a division of its vertices into two disjoint subsets, A and A. Without loss of generality, we can assume that jAj A . Let E (A; A) be the set of edges with one endpoint in A and the other in A. The cut size of the partition (A; A) is simply jE (A; A)j. The cut ratio, or simply the ratio of the cut, denoted (A; A), is equal to the ratio of the size of the cut to the size of A, namely, jE )j (A; A) = min((jA;j;AAj) : A j The isoperimetric number of a graph, which measures how good a ratio cut one can hope to nd, is de ned to be E (A; A) (G) = jAmin 2 jAj : j n=

In Section 7, we describe a relation between the isoperimetric number of a graph and its Fiedler value. A partition is a bisection of G if A and A di er in size by at most 1. For in the range 0< 1=2, a partition is called a -separator if min(jAj; jAj) n. We use the word cut to refer to a partition separating any number of vertices and reserve the word separator for partitions that are -separators for some > 0. Given an algorithm that can nd cuts of ratio in G and its subgraphs, we can nd a bisector of G of size O ( n) (see Lemma 22). The adjacency matrix, A(G), of a graph G is the n n matrix whose (i; j )-th entry is 1 if (i; j ) 2 E and 0 otherwise. The diagonal entries are de ned to be 0. Let D be the n n diagonal matrix with entries Di;i = di, where di is the degree of the ith vertex of G. The Laplacian, L(G), of the graph G is de ned to be L(G) = D ? A. Let M be an n n matrix. An n-dimensional vector ~ is an eigenvector of M if there is a scalar x such that M~ = ~ . is the eigenvalue of M corresponding to the eigenvector ~ . If M is a real x x x symmetric matrix, then all of its n eigenvalues are real. The only matrices we consider in this paper will be the Laplacians of graphs. Notice that the all-ones vector is an eigenvector of any Laplacian matrix and that its associated eigenvalue is 0. Because Laplacian matrices are positive semide nite, all the other eigenvalues must be non-negative. We will focus on the second smallest eigenvalue, u 2 , of the Laplacian and an associated eigenvector ~ . Fiedler called this eigenvalue the \algebraic connectivity of a graph", so we will call it the Fiedler value and an associated eigenvector a Fiedler vector. 4

2.2. Laplacians and Fiedler Vectors

The following properties of Fiedler values and vectors play an important role in this paper: The Fiedler value of a graph is greater than zero if and only if the graph is connected. A Fiedler vector ~ = (u1; :::; un) satis es u n X ui = 0;

i=1

because all-ones vector is an eigenvector of the Laplacian and the eigenvectors of a symmetric matrix are orthogonal. The Fiedler value, 2 , of G satis es xT L( x min ~ ~ T G)~ ; 2 = ~ ?(1;1;:::;1) x x~ x with the minimum occurring only when ~ is a Fiedler vector. x For any vector ~ 2 Rn , we have x X ~ T L(G)~ = x x (xi ? xj )2:

(i;j )2E

Let M be a symmetric n n matrix and ~ be an n-dimensional vector. Then, the Rayleigh x quotient of ~ with respect to M is x ~ T M~ : x x ~T~ xx For proofs of these statements and many other fascinating facts about the eigenvalues and eigenvectors of graphs consult one of Str88, Moh88, CDS90, Big93]. The Fiedler value, 2 , of a graph is closely linked to its isoperimetric number. If G is a graph on more than three nodes, then one can show AM85, Moh89, SJ88] q 2 (G) 2 (2d ? 2 ): 2 In Section 7, we will focus on the second inequality.

2.3. Spectral Partitioning Methods

Let ~ = (u1; :::; un) be a Fiedler vector of the Laplacian of a graph G. The idea of spectral u partitioning is to nd a splitting value s and partition the vertices of G into the set of i such that ui > s and the set such that ui s. We call such a partition a Fiedler cut. There are several popular choices for the splitting value s: bisection: s is the median of fu1; :::; ung. 5

ratio cut: s is the value that gives the best ratio cut. sign cut: s is equal to 0. gap cut: s is a value in the largest gap in the sorted list of Fiedler vector components.

Other variations have been proposed. In this paper, we will analyze the spectral method that uses the splitting value that achieves the best ratio cut. We will show that, for bounded-degree planar graphs and well-shaped meshes, it always nds a good ratio cut. In fact, it is not necessary to use a Fiedler vector; an approximation will su ce. If a vector ~ that is orthorgonal to the all-ones vector has a small Rayleigh quotient x with respect to the Laplacian of G, then ~ can be used to nd a good ratio cut of G. x Guattery and Miller GM95] showed that there exist bounded-degree planar graphs on n vertices with constant-size separators for which spectral bisection and spectral sign cuts give separators that cut n=3 edges. p We will show that planar graphs have Fiedler cuts of ratio O(1= n). By Lemma 22, our result p implies that a bisector of size O( n) can be found by repeatly nding Fiedler cuts. In Section 8, we extend the results of Guattery and Miller to show that this repeated application of Fiedler cuts is necessary, even for some quite natural graphs. We will show that, for any constant in the range 0 < 1=2, there are natural families of well-shaped two-dimensional meshes that have no Fiedler cut of small ratio that is also a -separator. We discuss why these graphs exist as well as why they might fail to arise in practice. Our explanation is not entirely satisfactory and the problem remains of nding a better characterization of the graphs that do arise in practice as well as those for which p there is a Fiedler cut that produces a -separator of size O( n).

3. The eigenvalues of planar graphs

In this section, we will prove that the Fiedler value of every bounded-degree planar graph is O(1=n). Our proof establishes and exploits a connection between the Fiedler value and geometric embeddings of graphs. We obtain the eigenvalue bound by demonstrating that every planar graph has a \nice" embedding in Euclidean space. A bound of O (1=pn) can be placed on the Fiedler value of any planar graph by combining the planar separator theorem of Lipton and Tarjan LT79] with the fact that 2=2 (G). Bounds of O (1=n) on the Fiedler values of planar graphs were previously known for graphs such as regular grids PSL90], quasi-uniform graphs GK95], and bounded-degree trees. Bounds on the Fiedler values of regular grids and quasi-uniform graphs essentially follow from the fact that the diameters of these graphs are large (see Chu89]). Bounds on trees can be obtained from the fact that every boundeddegree tree has a -separator of size 1 for some constant in the range 0 < < 1=2 that depends only on the degree. However, in order to estimate the Fiedler value of general bounded-degree planar graphs and well-shaped meshes, we need di erent techniques. p We denote the standard l2 norm of a vector ~ in Euclidean space by k~ k = xT x. We relate x x the quality of an embedding of a graph in Euclidean space with its Fiedler value by the following lemma: 6

Lemma 1 (embedding lemma). Let G = (V; E ) be a graph. Then 2, the Fiedler value of G, is given by P v v 2 )2 k~ i ? ~ k = min (i;jPnE k~ k2 j ; 2 i=1 vi where the minimum is taken over vectors f~ 1 ; : : :;~ n g Rn such that v v

n X i=1

~i = ~ ; v 0

where ~ denotes the all-zeroes vector. 0

Remark 2. While we state this lemma for vectors in Rn , it applies equally well for vectors in Rm

for any m 1.

n x2 i=1 i Pn x = 0. where the minimum is taken over real xi's such that i=1 i when (x1; : : :; xn) is an eigenvector.

Proof: Because the all-ones vector is the eigenvector of L(G) corresponding to the eigenvalue 0, 2 can be characterized by P 2 2E (x ? x ) = min (i;j)P i j ;

2

The minimum is achieved precisely

The embedding lemma now follows from a component-wise application of this fact. Write ~i as v Pn ~ = ~ , we have (vi;1; : : :; vi;n). Then, for all f~1; : : :;~ng such that i=1 vi 0 v v P P Pn 2 v v 2 (i;j )2E k~ i ? ~ j k (i;j )2E k=1 (vi;k ? vj;k ) = Pn k~ k2 Pn Pn v2 i=1 vi Pn Pi=1 k(=1 i;k v )2 v ? = k=1 P(ni;j)2E n i;k 2 j;k : P v k=1 i=1 i;k But, for each k, so

P

Pn P 2 k=1 (i;j )2E (vi;k ? vj;k ) Pn Pn v2 2 k=1 i=1 i;k (this follows from the fact that Pi xi= Pi yi mini xi=yi, for xi; yi > 0). 2 Our method of nding a good geometric embedding of a planar graph is similar to the way in which Miller, Teng, Thurston, and Vavasis MTTV96a] directly nd good separators of planar graphs. We rst nd an embedding of the graph on the plane by using the \kissing disk" embedding of Koebe, Andreev, and Thurston Koe36, And70a, And70b, Thu88]:

7

2 (i;j )2E (vi;k ? vj;k ) Pn v 2 i=1 i;k

2;

Theorem 3 (Koebe-Andreev-Thurston). Let G be a planar graph with vertex set V = f1; : : : ; ng and edge set E . Then, there exists a set of disks fD1 ; : : :; Dn g in the plane with disjoint interiors such that Di touches Dj if and only if (i; j ) 2 E .

Such an embedding is called a kissing disk embedding of G. The analogue of a disk on the sphere is a cap. A cap is given by the intersection of a half-space with the sphere, and its boundary is a circle. We de ne kissing caps analogously with kissing disks. Following MTTV96a], we use stereographic projection to map the kissing disk embedding of the graph on the plane to a kissing cap embedding on the sphere (See Section 4 for more information on stereographic projection). In Theorem 9, we will show that we can nd a sphere preserving map map that sends the centroid (also known as the center of gravity or center of mass) of the centers of the caps to the center of the sphere. Using this theorem, we can bound the eigenvalues of planar graphs: 8d : n p Accordingly, G has a Fiedler cut of ratio O (1= n), and one can iterate Fiedler cuts to nd a p bisector of size O ( n).

G is at most

Theorem 4. Let G be a planar graph on n nodes of degree at most d. Then, the Fiedler value of

Proof: By Theorem 3 and Theorem 9, there is a representation of G by kissing caps on the unit

sphere so that the centroid of the centers of the caps is the center of the sphere. Let ~1; : : :;~n be v Pn ~ = ~v. the centers of these caps. Make the center of the sphere the origin, so that i=1 vi 0 Let r1; : : :; rn be the radii of the caps. If cap i kisses cap j , then the edge from ~i to ~j will have v v length at most (ri + rj )2. As this is at most 2(ri2 + rj2), we can divide the contribution of this edge between the two caps. That is, we write n X X k~i ? ~j k2 2d ri2: v v

(i;j )2E

i=1

But, because the caps do not overlap,

n X i=1

ri2 4 :

Moreover, k~ik = 1 because the vectors are on the unit sphere. v Applying the embedding lemma, we nd that the Fiedler value of G is at most P v v 2 8d (i;j )2E k~ i ? ~ j k Pn kv k2 n: i=1 ~i Given the bound on the Fiedler value, the ratio achievable by a Fiedler cut follows immediately from Theorem 21 and the corresponding bisector size follows Lemma 22. 2 8

Remark 5. One can prove a slightly weaker result by using a result of Miller, Teng, Thurston,

and Vavasis MTTV96a] to nd a circle-preserving map that makes the center of the sphere a centerpoint Ede87] of the images of particular points in the caps. If the center of the sphere is a centerpoint, then the centroid must be far away from at least a constant fraction of the centers of the caps. Thus, the numerator of the Rayleigh quotient will be the same as in Theorem 4, and the denominator will be (n).

Remark 6. The embedding lemma can be viewed as a semi-de nite relaxation of an integer program

for minimum balanced cut. The integer program would be

min

X

s:t:

(i;j )2E n X xi = 0; and i=1 xi 2 f 1g :

(xi ? xj )2

However, unlike the semi-de nite relaxation of MaxCut used by Goemans and Williamson GW94], we do not know if our relaxation provides a constant factor approximation of the optimum.

4. Sphere-preserving maps

Let B d be the unit ball in d dimensions: f(x1; : : :; xd)j Pn=1 x2 1g. Let S d denote the sphere i i de ning the surface of B d. This section is concerned with sphere-preserving maps from S d to S d. A sphere-preserving map from S d to S d is a continuous function that sends every sphere (of lower dimension) contained in S d to a sphere in S d and such that every sphere in S d has a pre-image under the map that is also a sphere. Familiar sphere-preserving maps include rotations and the map that sends each point to its antipode. We will make use of a slightly larger family of sphere-preserving maps. We obtain this family by rst considering sphere-preserving maps between the sphere and the plane. Let H d be the hyperplane tangent to S d at (?1; 0; : : : ; 0). One can map H d to S d by stereographic projection: : H d ! S d by (z) = the intersection of S d with the line connecting z to (1; 0; : : : ; 0): Similarly, one de nes a map ?1 : S d ! H d that sends a point z 2 S d to the intersection of H d with the line through z and (1; 0; : : : ; 0). Note that ?1 is not well-de ned at (1; 0; : : : ; 0). To x this, we add the point 1 to the hyperplane H d , and de ne ?1(1; 0; : : : ; 0) = 1 as well as (1) = (1; 0; : : : ; 0). For any point 2 S d, we de ne to be the stereographic projection from the plane perpendicular to S d at , and we let ?1 be its inverse (so, (1) = ? ). One can show that the maps and ?1 are sphere-preserving maps (see HCV52] or MTTV96a] for a proof). 9

Sphere-preserving maps in the plane include rigid motions of the plane as well as dilations (and other mobius transformations). We will obtain sphere-preserving maps in the sphere by applying a projection onto a plane, then applying a dilation of the plane, and then mapping back by stereographic projection. Thus, for 2 S d and a 0, we de ne Da to be the map that dilates the hyperplane perpendicular to S d at by a factor of a (note that Da (1) = 1). For example,

D(a?1;0;:::;0) : (?1; x2; : : :; xd) 7! (?1; ax2; : : :; axd):

As the composition of sphere-preserving maps is again a sphere-preserving map, we can now de ne the sphere-preserving maps that we will use. For any such that k k < 1, de ne f (z) by

f (z) =

1?k k ?1 =k k(D =k k ( =k k(z ))):

It is routine to verify that f is continuous. We wish to extend the de nition of f to on S 2, even though the resulting maps will not be continuous. For k k = 1, we de ne ( f (z) = ? if z = ? , and otherwise. We will now examine the e ect of the maps f on arrangements of spherical caps on S d. Recall that a spherical cap on S d is a connected region of S d whose boundary is a (d ? 1)-dimensional sphere. Thus, the image of a cap under a map f is determined by the image of its boundary along with a point in its interior. For a cap C on S d , let p(C ) denote the point on S d that is the center of C (i.e., the point inside C that is equidistant from its boundary). We want to show that, for any arrangement of caps fC1; : : :; Cn g on S d, there is an 2 S d so that the centroid of fp(f (C1)); : : :; p(f (Cn))g is the origin. But rst, we must exclude some degenerate cases: De nition 7. An arrangement of caps fC1; : : :; Cng in S d is well-behaved if there is no point that belongs to at least half of the caps.

Remark 8. All of the arrangements of caps obtained from graphs contained in the other sections

of this paper are well-behaved. Otherwise, the induced graphs would have cliques on half of their vertices and no small separators.

Theorem 9. For any well-behaved arrangement of caps fC1; : : :; Cn g in S d, there is an so that k k < 1 and Pn

i=1 p(f

n

(Ci)) = ~ : 0

10

Consider the map from to the centroid of fp(f (C1)); : : :; p(f (Cn ))g. We want to ~ has a preimage under this map. This would be easier if the map were continuous, but show that 0 it is not continuous for k k = 1: as ? crosses the boundary of Ci, p(f (Ci)) jumps from one side of the sphere to the other. To x this problem, we construct a slightly modi ed map that is continuous. Because the set of caps is well-behaved, we can choose an > 0 so that, for all such that k k 1 ? , most of the caps ff (C1); : : :; f (Cn)g are entirely contained within the ball of radius 1=2n around =k k. In particular, this implies that f does not map the centroid of the centers of the caps to the origin. For 2 B d, we now de ne the map Pn w(C ; )f (p(C )) i ( ) = i=1 i n ; where the weight function w is given by ( w(C; ) = (2 ? d( ; C ))= if d( ; C ) 2 ? , and 1 otherwise, where by d( ; C ), we mean the greatest distance from to a point in the cap C (for example, if ? 2 C , then d( ; C ) = 1 + k k). We have chosen w to be a continuous function of that goes to zero as ? approaches the boundary of a cap; so, ( ) is also a continuous function. From the fact that fC1; : : :; Cn g is well-behaved, it is easy to verify that, for 2 S d, ( ) lies on the line connecting ~ to and is closer to than it is to ? . By combining this fact with some 0 elementary algebraic topology, we can use Lemma 10 to show that there is an such that ( ) = ~ . 0 By our choice of , k k < 1 ? , so all of the terms w( ; Ci ) are 1, which implies that f is the map that we were looking for. 2

Proof:

Lemma 10. Let : B d ! B d be a continuous function so that, for 2 S d, ( ) lies on the line connecting with ~ and is closer to than it is to ? . Then, there exists an 2 B d such that 0

( ) = ~. 0

Proof:

Assume, by way of contradiction, thatothere is no point n 0 Now, consider the map b( ( )), where b : B d ? ~ ! S d by

2 B d such that ( ) = ~ . 0

b(z) = z=kzk: Since b is a continuous map, b is a continuous map of B d onto S d that is the identity on S d. Then z 7! ?b( (z)) is a map from B d onto S d that has no xed point. This contradicts Brouwer's Fixed Point Theorem, which says that every continuous map from B d into B d has a xed point. 2 We have shown that, for most collections of balls in H d, there is a sphere preserving map from H d to S d such that the centroid of the centers of the caps is the origin. We now show that one can nd such a map by performing a rigid motion of H d followed by a dilation of H d followed by stereographic projection.

11

that belongs to at least half of the balls.

De nition 11. An arrangement of balls fD1; : : :; Dn g in H d is well-behaved if there is no point Theorem 12. Let fD1; : : :; Dn g be a well-behaved collection of balls. Then, there is a point x 2 H d

and an a > 0 such that the sphere preserving map

gx;a : z 7! (a(z ? x))

sends the balls to a collection of caps, the centroid of whose centers is the origin.

to a point on the line segment between and ~ . We can then apply Lemma 10 to prove that there 0 is some map such that the map g ? ( );(1?k k) sends the centroid of the centers of the caps to the origin. 2

1

Proof: sketch] For an 2 S d, consider the map g ? ( );(1?k k) followed by a rotation of the sphere that sends (?1; 0; : : :; 0) to . As we did in the proof of Theorem 9, we can construct a continuous map from to a weighted centroid of the centers of the caps, which for 2 S d sends

1

5. The Spectra of k-Nearest Neighbor Graphs

We extend our spectral planar separator theorem to graphs embedded in three and more dimensions. We show that Fiedler cuts of small ratio can be found in -overlap graphs of k-ply neighborhood systems. One corollary of this extension is that the spectral method nds small ratio cuts for k-nearest neighbor graphs and well-shaped nite element meshes in any xed dimension. In this section, we analyze intersection graphs and nearest neighbor graphs. Results on overlap graphs and well-shaped meshes will be given in the next section. In this section and the next, we will use the following notation: We use capital letters to denote balls in Rd . If A is a ball in Rd, then we will use A0 to denote its image on the sphere S d+1 under stereographic projection. If is a positive real and A is a ball of radius r, then A is the ball with the same center as A and radius r. Similarly, if A0 is a spherical cap of spherical radius r, then A0 is the spherical cap with the same center as A0 and radius r. Let Vd be the volume of a unit d-dimensional ball. Let Ad be the surface volume of a unit d-dimensional ball.

5.1. Intersection Graphs

The graphs that we consider are de ned by neighborhood systems. A neighborhood system is a set of closed balls in Euclidean space. A k-ply neighborhood system is one in which no point is contained in the interior of more than k of the balls. Given a neighborhood system, ? = fB1; : : : ; Bng, we de ne the intersection graph of ? to be the undirected graph with vertex set V = fB1; : : :; Bn g and edge set E = f(Bi; Bj ) : Bi \ Bj 6= ;g : 12

For example, the Koebe-Andreev-Thurston embedding theorem says that every planar graph is isomorphic to the intersection graph of some 1-ply neighborhood system in two dimensions. Let P = fp1; : : : ; png be a point set in Rd . For each pi 2 P , let Nk (pi ) be the set of k points closest to pi in P (if there are ties, break them arbitrarily). A k-nearest neighbor graph of P is a graph with vertex set fp1; : : : ; png and edge set E = f(pi; pj ) : pi 2 Nk (pj ) or pj 2 Nk (pi)g: Miller et. al. MTTV96b] show that every k-nearest neighbor graph in Rd is a subgraph of an intersection graph of a d k-ply neighborhood system, where d is the kissing number in d dimensions|the maximum number of nonoverlapping unit balls in Rd that can be arranged so that they all touch a central unit ball CS88]. Moreover, the maximum degree of a k-nearest neighbor graph is bounded by dk.

5.2. A Spectral Bound

Proof:

such that the maximum degree of G is . Then, the Fiedler value of L(G) is bounded by cd (k=n)2=d, where cd = 2(Ad+1 =Vd )2=d.

Theorem 13. Let G be a subgraph of an intersection graph of a k-ply neighborhood system in Rd

Let ? = fB1; :::; Bng be the k-ply neighborhood system of which G is the intersection graph. By Theorem 9, there exits a sphere-preserving map : Rd ! S d such that the centroid of the centers of the images of the Bi 's is the center of the sphere. 0 Let (?) = fBi0; :::; Bng be the images of the balls in ? under . Then, the balls in (?) also form a k-ply system. Let ri be the radius of Bi0. Because Vdrid volume(Bi0), n n X d X (1) volume(Bi0) kAd+1: Vd ri By Lemma 1,

i=1 i=1

Pn 2 r2 i=1 i 2 (L(G)) n d 2=d 1?2=d (2 ) (kAd+1=Vn) n ! Ad+1 2=d k 2=d : (2 ) V n d Note that the second inequality follows from (1). 2 The next two corollaries follow from Theorem 13, Theorem 21, and Lemma 22. Corollary 14. The Fiedler value of a k-nearest neighbor graph of n points in Rd is bounded by O(k1+2=d=n2=d). Therefore, G has a Fiedler cut of ratio O k1+1=d=n1=d , and one can repeatedly take Fiedler cuts to nd a bisector of size O k1+1=d n1?1=d .

13

Corollary 15. Let G be a subgraph of an intersection graph of a k-ply neighborhood system in Rd

whose maximum degree is . Then, G has a Fiedler cut of ratio O iterate Fiedler cuts to obtain a bisector of size O 1+1=dn1?1=d .

1+1=d=n1=d

, and one can

6. The Spectra of Well-Shaped Meshes

One of the main applications of the spectral method is the partitioning of meshes for parallel numerical simulations. Many experments demonstrate the e ectiveness of this method BS92, HL92, HL93, PSL90, Sim91, Wil90]. In this section, we explain why the spectral method nds such good partitions of well-shaped meshes.

6.1. Well-Shaped Meshes

Most numerical methods work by approximating continuous problems with discrete problems on nite structures whose solutions can be e ciently computed. The nite structure used is often called a mesh. Many such methods have been developed and applied to important problems in mechanics and physics. Most of these numerical methods can be classi ed as equation based methods (e.g., the nite element, nite di erence, and nite volume methods) or particle methods (e.g., the N-body simulation method). However di erent the particular methods may be, a basic principle is common to all|accuracy of approximation is ensured by using meshes that satisfy certain numerical and geometric constraints. Meshes that satisfy these constraints are said to be well-shaped. To motivate our spectral analysis of well-shaped meshes, we review the conditions required of nite element and nite di erence meshes. More detailed discussions can be found in several books and papers (for example, see SF73, Joh92, BEG94, BE92, Fri72]). Background material on the particle method can be found in BH86, GR87, HE81, Zha87]. The nite element method approximates a continuous problem by subdividing the domain (a subset of Rd ) of the problem into a mesh of polyhedral elements and then approximates the continuous function by piecewise polynomial functions on the elements. A common choice for an element is a d-dimensional simplex. Accordingly, a d-dimensional nite element mesh is a ddimensional simplicial complex, a collection of d-dimensional simplices that meet only at shared faces BEG94, BE92, MT90]. The computation graph associated with each simplicial complex is often its 1-skeleton or the 1-skeleton of its geometric dual (as used in the nite volume method). In the nite element method, a linear system is de ned over a mesh, with variables representing physical quantities at the nodes. The nonzero structure of the coe cient matrix of such a linear system is exactly the adjacency structure of the 1-skeleton of the simplicial complex. To ensure accuracy, in addition to the conditions that a mesh must conform to the boundaries of the region and be ne enough, each individual element of the mesh must be well-shaped. A common shape criterion for the nite element method is that the angles of each element are not too small, or the aspect ratio of each element is bounded BA76, BEG94, Fri72]. Other numerical 14

formulations require slightly di erent conditions. For example, the controlled volume formulation Nic92, MTTW95] using a Voronoi diagram requires that the radius aspect ratio (the ratio of the circumscribed radius to the shortest edge length of an element in the dual Delaunay diagram) is bounded. The nite di erence method also uses a discrete structure, a nite di erence mesh, to approximate a continuous problem. Finite di erence meshes are often produced by inserting a uniform grid from R2 or R3 into the domain via a boundary-matching conformal mapping. Notice that, unlike a nite element mesh, a nite di erence mesh need not be a collection of simplices or elements, so we can not analyze it as we do a triangulation. In general, the derivative of the conformal transformation must vary gradually with respect to the mesh size in order to produce good results (See, for example TWM85]). This means that the mesh will probably satisfy a density condition BB87, MV91]. Let G be an undirected graph and let be an embedding of its nodes in Rd. We say is an embedding of density if the following inequality holds for all vertices v in G: Let u be the node closest to v. Let w be the node farthest from v that is connected to v by an edge. Then jj (w) ? (v)jj : jj (u) ? (v)jj In general, G is an -density graph in Rd if there exists an embedding of G in Rd with density . We will use the overlap graph to model well-shaped meshes (Miller et al MTTV96a]). An overlap graph is based on a k-ply neighborhood system. The neighborhood system and a parameter, 1, de ne an overlap graph: Let 1, and let ? = fB1; : : : ; Bng be a k-ply neighborhood system in Rd. The -overlap graph of ? is the graph with vertex set fB1; : : :; Bn g and edge set f(Bi; Bj ) : (Bi \ ( Bj ) 6= ;) and (( Bi) \ Bj 6= ;)g; where by B , we mean the ball whose center is the same as the center of B and whose radius is larger by a multiplicative factor of . Overlap graphs are good models of well-shaped meshes because each well-shaped mesh in two, three, or higher dimensions is a bounded-degree subgraph of some overlap graph (for suitable choices of the parameters and k). For example, Let M be a nite element mesh embedded in Rd in which every element has aspect ratio bounded by a. Then, there is a constant depending only on d and a so that the 1-skeleton of M is a subgraph of an -overlap graph of a 1-ply neighborhood system. Moreover its maximum degree is bounded by a constant that also depends only on d and a ( MTTV96a]). Let M be a Voronoi diagram (from a nite volume method) in Rd in which the radius aspect ratio of its dual Delaunay diagram is bounded by a. Then there is a constant depending only on d and a so that the dual Delaunay diagram is an -density graph ( MTTW95]). 15

6.2. Modeling Well-Shaped Meshes

If G is an -density graph in Rd, then the maximum degree of G is bounded by a constant depending only on and d; and, G is a subgraph of an -overlap graph of a 1-ply neighborhood system ( MV91, MTTV96a]). The computation/communication graph used in hierarchical N-body simulation methods (such as the Barnes-Hut's treecode method BH86] and the fast-multipole method GR87]) is a subgraph of an -overlap graph of an O(log n)-ply neighborhood system ( Ten96]). In this section, we show that an -overlap graph is a subgraph of the intersection graph obtained by projecting its neighborhoods onto the sphere and then dilating each by an O ( ) factor. By choosing the proper projection, we are able to use this fact to bound the eigenvalues of these graphs.

6.3. Spherical Embeddings of Overlap Graphs

1. Let A and B be balls in Rd such that

Theorem 16. Let

Then, (

(A \ ( B ) 6= ;) and (( A) \ B 6= ;): + + ) A0 touches ( + + ) B 0. Our proof uses two lemmas that handle orthogonal special cases.

r A

2α r C

S

Figure 1:

Lemma 17. Let A and C be balls in Rd equidistant from the origin and having the same radius.

Let A0 and C 0 be their images under stereographic projection onto S d+1 . If ( =2) A0 touches ( =2) C 0.

A touches

C , then

16

at distance at most 2 r from each other. Let S be the sphere centered at the origin that passes through the centers of A and C . The geodesic arc between the centers of A and C (on S ) has length at most 2 r =2. The portion of this arc that lies in the interior of A has length at least r (See Figure 1 for a two dimensional example). Since stereographic projection preserves the relations between the intersections of A and C with S , ( =2) A0 will touch ( =2) C 0. 2

Proof: Let r be the radius of A and C . Because A touches C , the centers of A and C are

a

b

Figure 2: Restriction to the plane through the top of the sphere, the origin, and the centers of A and B .

are colinear and the origin does not lie on the line segment between the center of A and the center of B . If A is closer to the origin than B and A touches B , then A0 touches B 0.

Lemma 18. Let A and B be balls in Rd so that the center of A, the center of B , and the origin Proof: We will restrict our attention to the plane through the top of the sphere, the origin, and

the centers of A and B (see Figure 2). Let a denote the interval that is the intersection of A with the plane. Observe that an interval of the same size as a but located further to the right on the line will have a smaller projection on the circle. The lemma follows. 2 Proof: of Theorem 16] Let A and B be any two balls in Rd and let A0 and B 0 be their images under stereographic projection on S d+1. Assume that A touches B and B touches A. We will show that ( + + ) A0 touches ( + + ) B 0. Assume, without loss of generality, that A is at least as large as B . Let C be the disk of the same distance to the origin as A and congruent to A that is closest to B . Then, the centers of C and B are colinear with the origin (See Figure 3). Let C 0 be the image of C . Since C is closer to B than A is, C touches B and B touches A. By Lemma 18, C 0 touches B 0. 17

A C

B

Figure 3: C is the circle congruent to and equidistant from the center to A that is closest to B . The distance between the centers of A and B is less than ( + 1) times the radius of A (because we assume that A is at least as large as B ). The same holds for the distance between the center of C and the center of B . Therefore, ( +1) A touches ( +1) C , so Lemma 17 implies that ( +1)=2 A0 touches ( + 1)=2 C 0. Since A0 and C 0 have the same spherical radius, C 0 ( ( + 1) + )A0. Thus, ( + + ) A0 must touch ( + + ) B 0. 2

6.4. A Spectral Bound

We now show that the Fiedler value of a bounded degree subgraph of an -overlap graph is small.

2(k=n)2=d , (k=n)1=d

the maximum degree of G is , then the Fiedler value of L(G) is bounded by d d = 2( + 1 + = )2(Ad+1 =Vd )2=d . Accordingly, G has a Fiedler cut of ratio O one can iterate Fiedler cuts to obtain a bisector of size O k1=dn1?1=d .

Theorem 19. If G is a subgraph of an -overlap graph of a k-ply neighborhood system in Rd and

where , and

G. By Theorem 12, there is a stereographic projection from Rd onto a particular sphere S d+1 so that the centroid of the centers of the images of the neighborhoods is the center of the sphere. 0 Let (?) = fBi0; :::; Bng be the images of the balls in ? under . Let ri be the radius of Bi0. Because Vdrd volume(Bi0), We know that n n X d X volume(Bi0) kAd+1: Vd ri

i=1 i=1

Proof: Let ? = fB1; :::; Bng be the k-ply neighborhood system whose intersection graph contains

18

By Theorem 16, G is a subgraph graph of the intersection graph of f( + + ) Bi0 : 1 i ng. Thus, by Lemma 1, Pn 2 ( + + ) 2 r 2 i=1 i 2 (L(G)) n 2=d k !2=d 2 Ad+1 (2 )( + + ) V n :

d

Given the bound on the Fiedler value, the ratio achievable by a Fiedler cut follows immediately from Theorem 21 and the corresponding bisector size follows Lemma 22. 2

Remark 20. Recently, Agarwal and Pach AP95] and, independently, Spielman and Teng ST96]

gave an elementary proof of the sphere separator theorem of Miller et al MTTV96b] on planar graphs and intersection graphs. However, these proofs do not directly extend to overlap graphs. The relation between overlap graphs and intersection graphs established by Theorem 16 enables us to prove the overlap graph separator theorem using the intersection graph separator theorem. The same reduction also extends the deterministic linear time algorithm for nding a good sphere separator from intersection graphs to overlap graphs EMT95].

7. Good ratio cuts

Alon Alo86] and Sinclair and Jerrum SJ88] proved that graphs with small Fiedler eigenvalue have a good ratio cut (Alon's theorem actually demonstrates the existence of a small vertex separator). A corollary of an extension of their work by Mihail Mih89] demonstrates that one can obtain a good ratio cut from any vector with small Rayleigh quotient that is perpendicular to the all-ones's vector (although this is not explicitly stated in her work). In this section, we will present a new proof of Mihail's theorem (see also AM85, Fil91, DS91, Mih89] and Moh89] for a tighter bound).

x x 2: ~ T Q~ ~ T ~ 2d xx Moreover, there is an s so that the cut (fi : xi sg ; fi : xi > sg) has ratio at most 2=(2d).

Theorem 21 (Mihail). Let G = (V; E ) be a graph on n nodes of maximum degree d, let Q be its Laplacian matrix, and let be its isoperimetric number. For any vector ~ 2 Rn such that x P

n x i=1 i

= 0,

Proof: Assume, without loss of generality, that x1 x2 xn, and consider the embedding of G in R by ~ . For i n=2, at least i edges must cross over xi. Similarly, for i n=2, at least x (n ? i) edges must cross xi. We will use this fact to show that the Rayleigh quotient of ~ cannot x

be too small. In our proof, we will deal with the i n=2 and the i n=2 similarly. To simplify matters, assume that n is odd. To achieve symmetry, we will work instead with the vector ~, where yi = xi ? x(n+1)=2, y 19

so that y(n+1)=2 = 0. In a moment, we will show that

~ T Q~ ~ T Q~ ; x x y y ~T~ xx ~T ~ y y so it su ces to nd a lower bound for the Rayleigh quotient of ~ with respect to Q. Recall that y P ~ T Q~ = (i;j)P (xi ? xj )2 : x x 2E n x2 ~T~ xx i=1 i Since (xi ? xj ) = (yi ? yj ), the inequality follows from n n n X X 2 X xi ? 2x(n+1)=2 xi + nx2n+1)=2 ~ T ~ = (xi ? x(n+1)=2)2 = y y ( i=1 i=1 i=1 n X 2 xi + nx2n+1)=2 (recall P xi = 0) = ( i=1 n X 2 T xi = ~ ~ : xx

i=1

So that we can treat the i < (n + 1)=2 and the i > (n + 1)=2 independently, we would like to eliminate all edges (i; j ) where i < (n + 1)=2 < j . Actually, we will replace each such edge with two ~ edges: one from i to (n + 1)=2 and one from (n + 1)=2 to j . Let E denote this new set of edges. ~ ~ ~ Also, let E? be those edges (i; j ) 2 E such that i; j (n + 1)=2, and let E+ be the others. Because 2 (yj ? y 2 + (y 2 , we nd (yj ? yi) (n+1)=2) (n+1)=2 ? yi) P P 2 2 ~ (i;j )2E (yi ? yj ) (i;j )2E (yi ? yj ) Pn y 2 Pn y 2 i=1 i P i=1y i ? y )2 + P 2 ~ ~ j (i;j )2E? ( i (i;j )2E (yi ? yj ) = : P(n+1)=2 y2 + Pn 2 i=1 i i=(n+1)=2 yi

+

We now prove a lower bound on the terms involving i (n + 1)=2. As a similar bound will hold for the other terms, the combination of the two will prove the theorem. The di culty in proving a bound on the Rayleigh quotient of ~ is that the numerator is composed y 2, while the denominator is a sum of y 2's. To overcome this problem, we would of terms like (yi ? yj ) i like to bound the terms (yi ? yj )2 by a combination of yi2 and yj2. Since yi and yj are usually separated, we can nd a bound that usually works. For any a > 0, the inequality y2 ? (1 + a)y2 (yi ? yj )2 i 1 + 1=a j ; follows from yi2 = (yi ? yj + yj )2 (1 + 1=a)(yi ? yj )2 + (1 + a)yj2: 20

We will choose a value for a later in the proof. For now, let d+ be the number of edges (i; j ) such i that j > i, let d? be the number such that j < i, and apply the inequality whenever i < j to obtain i P P ? 2 2 ~ ~ + (i;j )2E? (yi ? yj ) (i;j )2E? (di ? di (1 + a))yi : P(n+1)=2 y2 (1 + 1=a) Pn=2 yi2 i=1 i i=1 We will now choose a value of a so that P + ? 2 ~ (i;j )2E? (di ? di (1 + a))yi =2: Pn=2 y2 i=1 i Because the terms yi2 are strictly decreasing, it su ces choose a so that Pk (d+ ? d? (1 + a)) i i=1 i =2; k for all 1 k n=2. Since Pk=1 d+ is the number of edges with an endpoint less than yk and i Pk d? is the number of edgesi both of whose endpoints are less than y , their di erence is the k i=1 i number of edges that cross yk , which is at least k. Moreover, since the maximum degree of a node is d, Pk d? (d ? k)=2. Thus, a su cient constraint on a is that

k ? a(d ? )k=2 =2 ) a =(d ? ): k If we set a = =(d ? ), then (1 + 1=a) = d= , and we obtain a lower bound on the quotient of

2d : We now explain how to use good ratio cuts to produce a bisection of a graph.

2

i=1 i

2

Lemma 22. Assume that we are given an algorithm that will nd a cut of ratio at most (k) in every k-node subgraph of G, for some monotonically decreasing function . Then repeated application of this algorithm can be used to nd a bisection of G of size at most

Zn

Proof: The following algorithm (see LT79, Gil80]) will nd the bisection.

i. Initially, let D(0) = G, let A and B be empty sets, and let i = 0. ii. If D(i) is empty, then return A and B ; otherwise repeat (a) Find a cut of ratio at most (jD(i)j) that divides D(i) into F (i) and F (i). We assume that jF (i)j jF (i)j. 21

x=1

(x)dx:

(b) If jAj jB j, let A = A F (i); otherwise, let B = B F (i); (c) Let D(i+1) = F (i+1), let i = i + 1, and return to step (a). We assume that the algorithm terminates after t iterations. To show that this algorithm produces a bisection, we need to prove that, for all i in the range 0 i < t, min(jAj; jB j) + jF (i)j n=2. Because jF (i)j jF (i)j, min(jAj; jB j) + jF (i)j (jAj + jB j + jF (i)j + jF (i)j)=2 = n=2: We now analyze the total cut size. Because the algorithm nds cuts of ratio at most (jD(i)j) at the ith iteration, the number of edges we cut to separate F (i) is at most jF j (i) j)jF (i)j = X (jD(i) j) (jD

(i)

=

j =1 jD(i) j?jF (i) j+1 X

j =jD(i) j jD(i) j?jF (i) j+1 X j =jD j

(i)

(jD(i)j) (j )

The inequality follows from the fact that is monotonicly decreasing. The total number of edges cut by this algorithm is at most

t?1 X i=0

(jD(i)j)jF (i)j =

0 t?1 X X @jD j?jF

(i)

(i)

j+1

i=0 n X

j =jD(i) j

1 (j )A

j Z=1 n

1

(j ) (x)dx

The last inequality follows from the assumption that is monotonically decreasing.

2

Remark 23. If (x) = x?1=d then

Zn

1

Lipton and Tarjan LT79] showed that by repeatedly applying an -separator of size n, one p p can obtain a bisection of size =(1 ? 1 ? ) n. Gilbert Gil80] extended this result to graphs p with positive vertex weights at the expense of a 1=(1 ? 2) factor in the bisection bound. Djidjev and Gilbert DG92] further generalized this result to graphs with arbitrary weights. Leighton and Rao LR88] showed that one can obtain an O( )-approximation to a 1/3-separator from an -approximation to a ratio cut. 22

d (x)dx = d ? 1 (n1?1=d ? 1):

p

8. When Small Fiedler Cuts Are Unbalanced

Recall that a Fiedler cut of a graph is obtained by taking its Fiedler vector (x1; : : :; xn) and a splitting value s and cutting the edges that cross s. In this section, we present examples of planar graphs for which there is no balanced Fiedler cut of good ratio. In fact, we show that no eigenvector corresponding to a small eigenvalue has a splitting value that induces a good balanced cut. These graphs are generalizations of graphs constructed by Guattery and Miller GM95]. The properties that we demand of these graphs are easy to achieve, and the reader should be able to generalize our techniques to construct examples in many di erent contexts. Recently, Guattery and Miller GM96] have extended our extensions of their work to produce bounded-degree planar graphs in which the ratio achieved by any Fiedler cut is far from the graph's isoperimetric number. p All of our example graphs have cuts of ratio O (1= n) that separate o(n) nodes. This is necessary. In Section 3, we proved that every planar graph has a splitting value that induces a cut of ratio p Thus, if there is no unbalanced Fiedler cut of ratio O (1=pn), then the Fiedler cut of O (1= n). p ratio O (1= n) must be balanced. This might explain why most graphs that arise in practice have balanced Fiedler cuts: a fairly regular planar graph should not have a cut of ratio O (1=pn) that separates few vertices. The graphs that we build in this section will be constructed from: Pk , the path graph on k vertices (V = f0; : : : ; k ? 1g and E = f(i ? 1; i) : 1 i < kg), Rk , the ring graph on k vertices (V = f0; : : :; k ? 1g and E = f(i; i + 1 mod k) : 1 i kg), Wi;j , the Cartesian product of Pi with Rj , and Bi, the complete binary tree with 2i leaves and a total of 2i+1 ? 1 nodes.

Proposition 24. The Fiedler value of Pk (the path graph of k vertices) is equal to

The Fiedler vector ~ is given by u The s-th eigenvalue of Pk is equal to

4 sin2 2k :

? ~ i = cos (2i 2k1) u

4 sin2 (s ? 1) 2k

!

:

!

:

Its eigenvector ~ is given by u

~ i = cos (2i ? 1)(s ? 1) u 2n

23

!

:

Proposition 25. The Fiedler value of Rk is equal to

A Fiedler vector ~ is given by u

4 sin2 k :

i ~ i = cos 2k u

Proposition 26. Let G be the Cartesian product of graphs G1 and G2. Then the eigenvalues of G

are equal to all the possible sums of eigenvalues of G1 and G2. Therefore, the Fiedler value of G is the smaller of the Fiedler values of G1 and G2 .

We now consider graphs Sk;a;b obtained by joining one copy of Wa;b with two copies of Pk , which we label Pk and Pk0 . Label the vertices of Wa;b by fwi;j g, for 0 i < a and 0 j < b. Similarly, label the vertices of Pk and Pk0 by pi and p0i for 0 i < k. The graph Sk;a;b contains the edges of Wa;b, Pk , and Pk0 , as well as edges connecting w0;i to pk?1 and wa?1;i to p0k?1, for all 0 i < k (See Figure 4).

Pk

P’ k

Wa,b

Figure 4: Sk;a;b: despite the picture, the graph is planar. We now examine what a Fiedler vector of Sk;a;b looks like. We will write a Fiedler vector of Sk;a;b as (~; w; p0). p~ ~ Proposition 27. Let ~ = (~; w; p0) be a Fiedler vector of Sk;a;b. If k > b > a, then it cannot be the u p ~ ~ ~0 = ~ . case that p = p 0 ~ 24

Proof: If ~ = p0 = ~ , then the Fiedler value of Sk;a;b is at least the Rayleigh quotient of w with p ~ 0 ~

respect to the Laplacian of Wa;b: all the terms on the bottom of the Rayleigh quotient of ~ with u respect to L(Sk;a;b) appear on theobottom, and some extra terms appear on the top corresponding n to the edges between pk?1 ; p0k?1 and Wa;b. This would imply that the Fiedler value of Sk;a;b is at least the Fiedler value of Wa;b, which in turn larger than the Fiedler value of P2k?1 . This is a contradiction because the Fiedler value of P2k?1 is an upper bound on the Fiedler value of Sk;a;b: construct a vector in which the terms corresponding to pk?1 , p0k?1 , and Wa;b are zero, and the remaining nodes are set to the values of the Fiedler vector of P2k?1 . 2 1 j < k b.

Proposition 28. Let (~; w; p0) be a Fiedler vector of Sk;a;b, for k > b > a. Then wi;j = wi;k for all p~ ~

Proof: Consider the automorphism of Sk;a;b that maps wi;j to wi;(j+1 mod b) and leaves Pk and Pk0 xed. Assume, by way of contradiction, that (~ ) ? ~ = ~ . Then, (~ ) ? ~ is a Fiedler vector u u6 0 u u

in which the paths Pk and Pk0 get mapped to zero. This would contradict Proposition 27.

at least b edges or separates fewer than 2k vertices.

2

Theorem 29. Let k > b > a. Then, any Fiedler cut of the (ab + 2k)-node graph Sk;a;b either cuts

We now prove a similar statement for a bounded-degree planar graph. We do this by replacing the star graph in Sk;a;b with a complete binary tree. For b a power of two, we de ne the graph Tk;a;b to be a graph with two copies of Pk , which we call Pk and Pk0 , two copies of Bb, which we call Bb and Bb', and one copy of Wa;b. These graphs are linked by identifying the leaves of Bb with the nodes fw0;igi and the leaves of Bb0 with the nodes fwa;igi so that the graph is symmetric, the rightmost leaf of Bb maps to w0;0, and the graph remains planar. We attach Pk and Pk0 by identifying pk?1 with the root of Bb and p0k?1 with the root of Bb0 (See Figure 5).

p

k?1

Proof: Immediate from Propositions 27 and 28.

2

p’

Pk Bb W a,b B’ b

k?1

P’ k

Figure 5: Tk;a;b 25

In order to prove a statement similar to Proposition 27, we need to lower bound the Fiedler value of T0;a;b. We do this by proving a lower bound on the isoperimetric number of T0;a;b and then applying Theorem 21.

Proposition 30. For a b, Proof:

(T0;a;b) 1=(b + 1):

Let (A; A) be a cut of T0;a;b in which jAj A . Assume that r nodes of A are in the portion of T0;a;b that is Wa;b, and that t nodes of A are in the internal nodes of the trees Bb and Bb0 . Let I = fi : 9j for which wi;j 2 Ag ; and J = fj : 9i for which wi;j 2 Ag : If jI j < a, then for each j 2 J , there is an i such that (wi;j ; wi+1;j ) 2 E (A; A). Similarly, if jJ j < b, then for each i 2 I , there is an i such that (wi;j ; wi;j+j ) 2 E (A; A). Thus, E (A; A) is at least the minimum of a, b, and max fjI j ; jJ jg. Since, r jI j jJ j, E (A; A) is at least the minimum of a, b, p and r. The number of edges that leave the t vertices contained in the trees is at least t. Unless jI j = a, an edge must be cut for each of these edges. If jI j p a, then E (A; A)= jAj 1=(1 + b). Otherwise, = E (A; A) is at least the maximum of t and min(a; r). Since jAj is t + r, we nd

E (A; A) jAj

max(t; min(pr; a)) t+r

1=(1 + b):

2

2

1 Corollary 31. The Fiedler value of T0;a;b is at least 8(b+1) . Proof: Apply Theorem 21, observing that the maximum degree of T0;a;b is 4.

2

Proposition 32. Let ~ = (~; ~; w; ~0; p0) be a Fiedler vector of Tk;a;b. If k=2 > b > a, then it u pb~b ~

cannot be the case that ~ = p0 = ~ . p ~ 0

Proof: If ~ = p0 = ~ , then the Fiedler value of Tk;a;b is at least the Rayleigh quotient of (~ ; w; ~0) p ~ 0 b~b

with respect to the Laplacian of T0;a;b: all the terms on the bottom of the Rayleigh quotient of ~ with u respect to L(Tk;a;b) appear on the bottom, and some extra terms appear on the top corresponding o n to the edges between pk?1 ; p0k?1 and Bb and Bb0 . This would imply that the Fiedler value of Tk;a;b is at least the Fiedler value of T0;a;b, which in turn larger than the Fiedler value of P2k?1. This is a contradiction because the Fiedler value of P2k?1 is an upper bound on the Fiedler value of Tk;a;b. We can construct a vector in which the terms corresponding to pk?1 , p0k?1, Bb, Bb0 and Wa;b are zero, and the remaining nodes are set to the values of the Fiedler vector of P2k?1. 2 26

wi;j = wi;k for all 1

Proposition 33. Let ~ = (~; ~; w; ~0; p0) be a Fiedler vector of Tk;a;b for k=2 > b > a. Then u pb~b ~

depends on its height in the tree.

j<k

b. Moreover the value assigned to a node in one of the trees only

Proof:

We rst show that the children of the roots of the trees must have the same value. Consider the automorphism of Tk;a;b induced by swapping wi;j with wi;b?j?1. By an argument similar to that used in the proof of Proposition 28, we see that the values assigned by the Fiedler vector to wi;j and wi;b?j?1 must be identical, and the same holds for the tree nodes paired by the mapping. We can now work our way down the tree. The maps that we use will not necessarily be automorphisms, but they will take advantage of the identi cation of values that we have established before. Next, we consider the mapping induced by swapping wi;j with wi;b=2?j?1, for 0 j < b=2, and wi;b=2+j with wi;b?j?1 , for 0 j < b=2. This must again produce a Fiedler vector. By applying an argument such as that in the proof of Proposition 28, we obtain more identi cations of values. We conclude the proof by continuing this way down the subtrees. 2

Theorem 34. Let k=2 > b > a. Then, any Fiedler cut of the (ab +2(b ? 1)+2(k ? 1))-node graph

Tk;a;b either cuts at least b edges or separates fewer than 2k vertices.

For su ciently large k, no eigenvector of a small eigenvalue of Tk;a;b will produce a balanced cut of small ratio. To prove this, we show that the columns of Wa;b map to the same point in these eigenvectors as well. We rely on the Courant-Fisher characterization of the eigenvalues of a matrix, which is a generalization of Rayleigh's characterization. Proposition 35 (Courant-Fisher). Let M be an n n real symmetric matrix. Let k (M ) denote its k-th smallest eigenvalue. Then ~ T M~ x x k = min max T ; U ~ 2U ~ ~ x xx where U ranges over all k-dimensional subspaces of Rn .

Proof: Immediate from Propositions 32 and 33.

2

Corollary 36. For 0 < i < k,

1 j i + 1 such that

i+1 (Tk;a;b )

2i (P2k?1 ):

Proof: To bound

i+1 (Tk;a;b), we

will construct a set of i + 1 vectors ~ j = (~j ; ~j ; wj ; ~0j ; p0j ), for x p b ~ b ~

T

1

j +1

x ( x max x ) ~ L~Tk;a;b)~ = 2i(P2k?1): T~ x ~ 2span(~ ;:::;~ x xx Let ~j be the eigenvector of P2k?1 corresponding to j . Since ~1 is the all-ones vector, we let ~ 1 v v x be the all-ones vector. We now build the other ~ j 's from the even eigenvectors of P2k?1 Since ~2j x v

27

maps the middle vertex of P2k?1 to zero, we can build an analogous vector ~ j+1 by setting all of x the middle nodes of Tk;a;b to zero and making the paths on the end correspond to the values of ~2j . v ~ j+1, wj+1, and b0j+1 to be zero vectors, and we then assign values to ~j+1 and p0j+1 ~ ~ p That is, we set b ~ so that the resulting embedding of Tk;a;b resembles the embedding of P2k?1 under ~2j , except that v there is a large mass at zero. We conclude by applying Proposition 35. 2

Corollary 37. Let k=4 (j ? 1) > b > a and 1 i j . Then, any cut from the i-th eigenvector of

Tk;a;b either cuts at least b edges or separates fewer than 2k vertices.

Before we conclude this section, we wish to point out some ways in which one can vary the construction of Tk;a;b without adversely e ecting its resistance to Fiedler cuts. First, it is not necessary to have two sets of paths and two sets of trees leaving the middle section: Using only one path will su ce, although it complicates the proof of Proposition 32. Second, it is not necessary to have dangling paths leaving the graph. One can obtain similar constructions in fully triangulated graphs. A nested chain of triangles (Figure 6) will serve in place of a path.

Proof: Follows by generalizing Proposition 32 and Proposition 33 with Corollary 36.

2

Figure 6: Nested triangles can substitute for path graphs.

9. Acknowledgements

We thank Michael Mandell for advice on algebraic topology, John Gilbert, Nabil Kahale, Gary Miller, and Horst Simon for helpful discussions on the spectra of graphs, and Edmond Chow, Alan Edelman, Steve Guattery, Bruce Hendrickson, Satish Rao, Ed Rothberg, Dafna Talmor, and Steve Vavasis for comments on an early draft of this paper.

References

AK95] C. J. Alpert and A. B. Kahng. Recent directions in netlist partitioning: A survey. Integration: The VLSI Journal, 19:1{81, 1995. 28

Alo86] AM85] And70a] And70b] AP95] AST90] BA76] Bar82] BB87] BE92] BEG94] BH84] BH86] Big93] Bop87]

N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83{96, 1986. N. Alon and V.D. Milman. 1 , isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory Series B, 38:73{88, 1985. E. M. Andreev. On convex polyhedra in lobacevskii space. Math. USSR Sbornik, 10(3):413{440, 1970. E. M. Andreev. On convex polyhedra of nite volume in lobacevskii space. Math. USSR Sbornik, 12(2):270{259, 1970. P. Agarwal and J. Pach. Combinatorial Geometry. Wiley-Interscience, 1995. Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing, pages 293{299. ACM, 1990. I. Babuska and A.K. Aziz. On the angle condition in the nite element method. SIAM J. Numer. Anal., 13(2):214{226, 1976. E. R. Barnes. An algorithm for partitioning of nodes of a graph. SIAM J. on Algebraic and Discrete Methods, 4(3):541{550, 1982. M. J. Berger and S. Bokhari. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Trans. Comp., C-36:570{580, 1987. M. Bern and D. Eppstein. Mesh generation and optimal triangulation. In F. K. Hwang and D.-Z. Du, editors, Computing in Euclidean Geometry, pages 23{90. World Scienti c, 1992. M. Bern, D. Eppstein, and J. R. Gilbert. Provably good mesh generation. Journal of Computer and System Sciences, 48:384{409, 1994. E. R. Barnes and A. J. Ho man. Partitioning, spectra and linear programming. Progress in Combinatorial Optimization, pages 13{25, 1984. J. Barnes and P. Hut. A hierarchical O(n log n) force calculation algorithm. Nature, (324):446{449, 1986. Norman Biggs. Algebraic Graph Theory. Cambridge University Press, New York, NY, second edition, 1993. R. Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science, pages 280{285, Los Angeles, October 1987. IEEE. 29

BS92] CDS90] Che70] Chu89] CR87] CS88] CS93] CSZ93] DG92] DH72] DH73] DS91] Ede87] EMT95] Fie73]

S. T. Barnard and H. D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Technical Report RNR{92{033, NASA Ames Research Center, 1992. Dragos M. Cvetkovic, Michael Doob, and Horst Sachs. Spectra of Graphs : Theory and Application. Academic Press, New York, 1990. J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In R. C. Gunning, editor, Problems in Analysis, pages 195{199. Princeton University Press, 1970. F.R.K. Chung. Diamaters and eigenvalues. Journal of the American Mathematical Society, 2(2):187{196, 1989. T. F. Chan and D. C. Resasco. A framework for the analysis and construction of domain decomposition preconditioners. Technical Report CAM-87-09, UCLA, 1987. J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. SpringerVerlag, 1988. T. F. Chan and B. Smith. Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes. Contemporary Mathematics, pages 1{14, 1993. P. K. Chan, M. Schlag, and J. Zien. Spectral k-way ratio cut partitioning and clustering. In Symp. on Integrated Systems, 1993. H. N. Djidjev and J. R. Gilbert. Separators in graphs with negative and multiple vertex weights. Technical Report CS-92-07, Xerox PARC, Palo Alto, 1992. W. E. Donath and A. J. Ho man. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15:938{944, 1972. W. E. Donath and A. J. Ho man. Lower bounds for the partitioning of graphs. J. Res. Develop., 17:420{425, 1973. P. Diaconis and D. Strook. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, 1(1):36{61, 1991. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, NY, 1987. D. Eppstein, G. L. Miller, and S.-H. Teng. A deterministic linear time algorithm for geometric separators and its applications. Fundamenta Informaticae, 22(4):309{330, April 1995. M. Fiedler. Algebraic connectibity of graphs. Czechoslovak Mathematical Journal, 23(98):298{305, 1973. 30

Fie75a] Fie75b] Fil91] Fri72] GHT84] Gil80] GK95] GM95] GM96] GR87] GW94] HCV52] HE81] HK92] HL92]

M. Fiedler. Eigenvectors of acyclic matices. Czechoslovak Mathematical Journal, 25(100):607{618, 1975. M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Mathematical Journal, 25(100):619{633, 1975. James Allen Fill. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. The Annals of Applied Probability, 1(1):62{87, 1991. I. Fried. Condition of nite element matrices generated from nonuniform meshes. AIAA J., 10:219{221, 1972. J.R. Gilbert, J.P. Hutchinson, and R.E. Tarjan. A separation theorem for graphs of bounded genus. Journal of Algorithms, 5:391{407, 1984. John Russell Gilbert. Graph Separator Theorems and Sparse Gaussian Elimination. PhD thesis, Computer Science Department, Stanford University, 1980. J. R. Gilbert and N. Kahale. personal communication, 1995. Stephen Guattery and Gary L. Miller. On the performance of the spectral graph partitioning methods. In Proceedings of The Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 233{242. ACM-SIAM, 1995. Stephen Guattery and Gary L. Miller. personal communication, 1996. L. Greengard and V. Roklin. A fast algorithm for particles simulations. J. of Comput. Phy., 73:325{348, 1987. Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the -42th Annual ACM Symposium on Theory of Computing, pages 422{431, 1994. D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea Publishing Company, New York, 1952. R. W. Hackney and J. W. Eastwood. Computer Simulation Using Particles. McGraw Hill, 1981. L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design, 11(9):1074{1085, September 1992. Bruce Hendrickson and Robert Leland. An impoved spectral graph partitioning algorithm for mapping parallel computation. Technical Report SAND92-1460, Sandia National Lab., December 1992. 31

Bruce Hendrickson and Robert Leland. The Chaco user's guide, Version 1.0. Technical Report SAND93-2339, Sandia National Lab., 1993. Joh92] C. Johnson. Numerical solution of partial di erential equations by the nite element method. Cambridge University Press, 1992. Koe36] Paul Koebe. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sachs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse, 88:141{164, 1936. LR88] F. T. Leighton and S. Rao. An approximate max- ow min-cut theorem for uniform multicommodity ow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 422{431, 1988. LT79] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. of Appl. Math., 36:177{189, April 1979. Mih89] M. Mihail. Conductance and convergence of Markov chains { a combinatorial treatment of expanders. In 30th Annual Symposium on Foundations of Computer Science, pages 526{531. IEEE, 1989. Moh88] B. Mohar. The Laplacian spectrum of graphs. In Sixth International Conference on the Theory and Applications of Graphs, pages 871{898, 1988. Moh89] B. Mohar. Isoperimetric numbers of graphs. Journal of Combinatorial Theory, Series B, 47:274{291, 1989. MT90] Gary L. Miller and William Thurston. Separators in two and three dimensions. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing, pages 300{ 309, Baltimore, May 1990. ACM. MTTV96a] G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Finite element meshes and geometric separators. SIAM J. Scienti c Computing, page to appear, 1996. MTTV96b] G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Separators for spherepackings and nearest neighborhood graphs. submitted to J. ACM, 1996. MTTW95] Gary L. Miller, Dafna Talmor, Shang-Hua Teng, and Noel Walkington. A Delaunay based numerical method for three dimensions: generation, formulation, and partition. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 683{692, Las Vegas, May 1995. ACM. MTV91] G. L. Miller, S.-H. Teng, and S. A. Vavasis. An uni ed geometric approach to graph separators. In 32nd Annual Symposium on Foundations of Computer Science, pages 538{547. IEEE, 1991. MV91] Gary L. Miller and Stephen A. Vavasis. Density graphs and separators. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 331{336, 1991. 32

HL93]

Nic92] PRS94] PSL90] PSS82] PSW92] SF73] Sim91] SJ88] SJ89] ST96] Str88] Ten91] Ten96] Thu88] TWM85]

R. A. Nicolaides. Direct discretization of planar div-curl problems. SIAM J. Numer. Anal., 29(1), 1992. S. Plotkin, S. Rao, and W. D. Smith. Shallow excluded minors and improved graph decomposition. In 5th Symp. Discrete Algorithms, pages 462{470. SIAM, 1994. A. Pothen, H. D. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl., 11:430{452, 1990. B. Parlett, H. Simon, and L. Stringer. Estimating the largest eigenvalues with the lanczos algorithm. Mathematics of Computation, 38:153{165, 1982. A. Pothen, H. D. Simon, and L. Wang. Spectral nested dissection. Technical Report CS{92{01, Pennsylvania State University Department of Computer Science, 1992. G. Strang and G. J. Fix. An Analysis of the Finite Element Method. Prentice-Hall, Englewood Cli s, New Jersey, 1973. H. D. Simon. Partitioning of unstructured problems for parallel processing. Computing Systems in Engineering, 2(2/3):135{148, 1991. A. J. Sinclair and M. R. Jerrum. Conductance and the rapid mixing property for markov chains: the approximation of the permanent resolved. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 235{244. ACM, 1988. Alistair Sinclair and Mark Jerrum. Approximative counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93{133, July 1989. D. A. Spielman and S.-H. Teng. Disk packings and planar separators. In Proceedings of 12th ACM Symposium on Computational Geometry, page to appear. ACM, May 1996. G. Strang. Linear Algebra and Its Applications. Harcourt Brace Jovanovich, Publishers, San Diego, CA, 1988. S.-H. Teng. Points, Spheres, and Separators: a uni ed geometric approach to graph partitioning. PhD thesis, Carnegie-Mellon University, School of Computer Science, 1991. CMU-CS-91-184. Shang-Hua Teng. Provably good partitioning and load balancing algorithms for parallel adaptive n-body simulation. SIAM J. Scienti c Computing (to appear), 1996. W. P. Thurston. The geometry and topology of 3-manifolds. Princeton University Notes, 1988. J. F. Thompson, Z. U. A. Warsi, and C. W. Mastin. Numerical Grid Generation: Foundations and Applications. New York, North Holland, 1985. 33

Ung51] Wil90] Zha87]

P. Ungar. A theorem on planar graphs. Journal London Math Soc., 26:256{262, 1951. R. D. Williams. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Technical report, California Institute of Technology, 1990. F. Zhao. An O(n) algorithm for three-dimensional n-body simulation. Technical Report TR AI Memo 995, MIT, AI Lab., October 1987.

34