Convergence theorems for some layout measures on random lattice and random geometric graphs

Convergence theorems for some layout measures on random lattice and random geometric graphs  Josep Daz y Mathew D. Penrose z Jordi Petit y Mara Serna y March 31, 1999 Abstract This work deals with convergence theorems and b ounds on the cost of several layout measures for lattice graphs, random lattice graphs and sparse random geometric graphs. For full square lattices, we give optimal layouts for the problems still op en. Our convergence theorems can be viewed as an analogue of the Beardwo o d, Halton and Hammersley theorem for the Euclidian TSP on random points in the d -dimensional cub e. As the considered layout measures are non-subadditive, we use p ercolation theory to obtain our results on random lattices and random geometric graphs. In particular, we deal with the sub critical regimes on these class of graphs. 1 Intro duction Layout problems on graphs aim to nd a linear ordering of the no des of an input graph such that a certain function is minimized. For the problems we consider b elow, nding an optimal layout is NP -hard in general, and therefore it is natural to develop and analyze techniques to obtain tight b ounds on restricted instances. Graphs enco ding circuits or grids are typical instances of linear arrangement problems. We consider these instances as sparse graphs that have clustering and geometric prop erties. For these classes of graphs, not much is known. In this pap er, we are concerned with lattice graphs, random instances of lattice graphs and random geometric graphs. For most of the layout problems it is an op en problem to nd exact or approximated p olynomial time algorithms for lattice graphs dierent than the full square lattice of side n and with n 2 points 9, 8, 7]. A graph is said to be a lattice graph if it is a no de-induced subgraph of the innite lattice, that is, its vertex set is a subset of Z 2 and twovertices are connected whenever they are at distance one. Percolation theory provides a framework to study lattice graphs in a  This researchwas partially supported byESPRITLTR Pro ject no. 20244 | ALCOM-IT, CICYT Pro ject TIC97-1475-CE, and CIRIT pro ject 1997SGR-00366. y Departament de Llenguatges i Sistemes Informatics. Universitat Politecnica de Catalunya. Campus Nord C6. c/ Jordi Girona 1-3. 08034 Barcelona (Spain). f diaz,jp etit,mjserna g @lsi.up c.es z Department of Mathematical Sciences, University of Durham, South Road, Durham DH1 3LE, England. Mathew.P[email protected] 1 probabilistic setting. We consider site p ercolation, where no des from the innite lattice are selected with some probability p (selected no des are called \op en"). Let C 0 b e the set of all op en no des connected by a path of op en no des to the origin. A basic question in p ercolation theory is whether or not C 0 can b e innite. Let # ( p ) denote the probabilitythat j C 0 j = 1 , and set p c =inf f p : # ( p ) > 0 g ,the critical value of p .It is well-known that p c 2 (0 : 5  1) 6]. In this pap er, we consider only subcritical limiting regimes p 2 (0 p c )inwhich all comp onents are almost surely nite. Results for supercritical regimes are derived in 4, 13 ]. In order to deal with b ounded graphs, weintro duce the class of random latticegraphs with parameters m and p denoted by L mp that corresp onds to the lattice graphs whose set of vertices are obtained through the random selection of each elementfrom f 0  ::: m ; 1 g 2 ,chosen indep endently with probability p . A random geometric graph G ( X n  r n ), with ( r n ) some chosen sequence of p ositivenumb ers, is dened byaset X n of n uniform and indep endently distributed p oints on 0  1] d and edges formed by joining any two dierent p oints at distance less or equal than r n . For an innite-volume analogue, let P  denote a homogeneous Poisson pro cess on R d of intensity  , and set P  0 = P  f 0 g . For n large, after appropriate scaling and centering at a randomly chosen p oint of X n , the graph G ( X n  r n ) lo oks lo cally like G ( P  0 1). We consider acontinuum site p ercolation pro cess based on the Poisson pro cess let e # (  )be the probability that the added poin tat the origin lies in an innite comp onent of G ( P  0  1). Then dene the critical p ercolation  c as the inmum of f > 0: e # (  ) > 0 g .It is well known 6] that  c 2 (0  1 ). In this pap er we shall deal with random geometric graphs satisfying the condition lim n !1 nr d n =  , for the sub critical regime < c . Our layout problems are formally dened as follows. A layout ' onagraph G =( V E ) is a one-to-one function ' : V !f 1  ::: n g with n = j V j . Given a graph G ,alayout ' on G and a number i<n , let us dene the sets: L ( i ' G )= f u 2 V ( G ) : ' ( u )  i g and R ( i ' G )= f u 2 V ( G ) : ' ( u ) >i g  the measures:  ( i ' G )= jf uv 2 E ( G ) : u 2 L ( i ' G ) ^ v 2 R ( i ' G ) gj   ( i ' G )= jf u 2 L ( i ' G ) : 9 v 2 R ( i ' G ): uv 2 E ( G ) gj   ( uv'G )= j ' ( u ) ; ' ( v ) j where uv 2 E ( G )  and the problems:  Minimum Linear Arrangement( MinLA ): Given a graph G =( V E ), nd minla ( G ) = min ' P uv 2 E  ( uv  ' G ) = min ' P n i =1  ( i ' G ). 2  Minimum Cut Width ( MinCut ): Given a graph G =( V E ), nd mincut ( G ) = min ' max n i =1  ( i ' G ).  Vertex Separation ( VertSep ): Given a graph G =( V E ), nd minvs ( G )=min ' max n i =1  ( i ' G ).  Minimum Sum Cut ( MinSumCut ): Given a graph G =( V E ), nd minsc ( G ) = min ' P n i =1  ( i ' G ).  Bisection ( Bisection ): Given a graph G =( V E ), nd minbis ( G ) = min '  ( b n= 2 c 'G ).  Vertex Bisection ( MinVertBis ): Given a graph G =( V E ), nd minvb ( G )=min '  ( b n= 2 c 'G ). The dened problems have imp ortant applications in several dierent areas, see for example 4]. With regard to their complexity, MinCut and VertSep remain NP -complete even when restricted to lattice graphs and geometric graphs 4]. For the remaining layout problems the complexity on lattice graphs and geometric graphs is op en. In this pap er, we rst present optimal layouts for minvs , minvb ,and minsc on full square lattices. Previously, the only known optimal layouts for these graphs were for mincut , minbis and minla 7, 9 , 8]. Results for the case of d -dimensional c -ary arrays (a generalization of square lattices) on the Bisection , MinCut and MinLA problems are presented in 10 ]. On the other hand, 11 ] presents a dynamic programming algorithm to solve Bisection on lattice graphs without holes. Then, we consider general lattice graphs, and we present upp er bounds for several layout problems on any lattice graph. Afterwards, we move to a randomized setting where we deal with random lattice and random geometric graphs. The main result for these graphs can be viewed as an analogue of the celebrated Beardwood, Halton and Hammersley theorem on the cost for the traveling salesman problem (TSP) on random p oints distributed in 0  1] d , BHH Theorem 1] . Let X = f X i g b e a sequence of indep endent and uniformly distributed points in 0  1] d .Let mintsp ( n ) denote the length of the optimal solution of the TSP among the rst n points of X . Then, there exists a constant  ( d ) such that mintsp ( n ) =n ( d ; 1) =d converges to  ( d ) almost surely as n !1 . Akey prop ertyto prove BHH-like results is geometric subadditivity (see Chapter 3 of 14]). This prop ertydo es not hold for our layout problems, therefore we take a completely dierent approach using p ercolation theory. Except for Bisection and MinVertBis ,one prop erty that all these problems share is monotonicity ,that is, the optimal value on a subgraph is always less than or equal to the optimal value in the whole graph. 3 01234567 0 1 2 3 4 5 6 7 1 2 3 4  n ; 1 n 2 3 4 n ; 1 n n 3 4 . . . n ; 1 n n n ; 1 4 n ; 1 n n n ; 1 . . . . . . n ; 1 n n n ; 1 . . . 4 n ; 1 n n n ; 1 4 3 n n ; 1 n ; 2  3 2 0 P n i =1 P n j = i j P n ; 1 i =2 i P n i =3 i ( i ; 2) Figure 1: Values of the vertex cut in the diagonal ordering ' D . 2 Bounds for lattice graphs We b egin this section bycharacterizing the optimal layouts for some of the problems dened in the previous section on square lattice graphs. Then we givesome deterministic upp er b ounds on the costs of the dened problems on nite subsets of the integer lattice Z 2 . Each subset L of vertices in Z 2 is identiedwitha lattice graph, namely the maximal subgraph of the 2-dimensional integer lattice with vertex set L .Let L n be the full n  n square lattice graph. The next results concern the optimalityof the diagonal ordering ' D on L n . In this ordering, x =( x y ) precedes x 0 =( x 0 y 0 ) whenever x + y<x 0 + y 0 , and whenever x + y = x 0 + y 0 and x<x 0 . Let 1  k < n 2 and x = ( x y ) such that ' D ( x ) = k . Dene r 2 Z + as follows: If x + y  n , then r = x + y ; 1, then wehave r ( r ; 1) = 2 <k  r ( r +1) = 2 and  ( k ' D L n )= r . If x + y>n with x 6 = n , then r =2 n ; ( x + y ) + 1, and when x = n then r =2 n ; ( x + y ). In this two last cases wehave r ( r ; 1) = 2 <n 2 ; k  r ( r +1) = 2and  ( k ' D L n )= r +1. In particular, for all k ,  ( k ' D L n )  n . See Figure 1. Prop osition 1 (Vertex isop erimetric inequality). For anylayout ' on L n and any k 2 f 1 ::: n 2 g ,wehav e  ( k  ' L n )   ( k ' D L n ). Proof. Given ' and k ,let A b e the set L ( k ' L n ), and let @ in A be the numb er of b oundary elements of A , i.e. elements of A having neighbours in L n n A .Thus @ in A =  ( k ' L n ). 4 Let A 0 b e the set in L n obtained by \pushing eachvertical section of A down as far as p ossible towards the x -axis" more precisely, setting S i ( A )= f j :( i j ) 2 A g for i 2f 1 ::: n g , let A 0 =  i 2f 1 :::n g : S i ( A ) 6 =  f i gf 1 :::  j S i ( A ) jg : Notice that j A 0 j = j A j , and it is not hard to checkthat @ in A 0  @ in A . Let A 00 be the set in L n , obtained by \pushing each horizontal section of A 0 sideways as far as p ossible towards the y -axis", in an analogous manner to the construction of A 0 from A . Then j A 00 j = j A 0 j = j A j , and @ in A 00  @ in A 0  @ in A: Moreover, A 00 is a down-set, that is, it has the prop erty that for any x 2 A 00 ,allvertices of L n lying directly b elow or directly to the left of x are in A 00 . Hence, without loss of generality, from now on we assume that A is adown-set. First supp ose (1 n ) = 2 A and ( n 1) = 2 A . Cho ose the p ositive integer r so that r ( r ; 1) = 2 <k  r ( r +1) = 2. Then there must b e a p oint x =( x y ) 2 A with x + y  r +1. Cho ose such a p oint x , having neighbours in L n n A b oth to its right and ab ove it. Then there is a path of y or more b oundary points of A from the b ottom of the square to x ,and another path of x or more b oundary p oints of A from the left of the square to x , and these paths do not intersect each other except at x . Therefore  ( k  ' L n )= @ in A = y + x ; 1  r: If r  n then we have  ( k ' D L n ) = r   ( k  ' L n ), while if r > n then we have  ( k ' D L n )  n   ( k  ' L n ). Thus we get the inequality claimed. Next supp ose (1 n ) 2 A and ( n 1) 2 A . Cho ose the p ositive integer r so that r ( r ; 1) = 2 <n 2 ; k  r ( r +1) = 2. Then there must b e a point x =( x y ) 2 L n n A with ( n +1 ; x )+( n +1 ; y )  r + 1, that is, x + y  2 n +1 ; r . Cho ose sucha point x ,having neighb ours in A b oth to its left and ab oveit. Then there is a path of at least n ; y + 1 b oundary p oints of A from the top of the square to the p oint just to the left of x , and another path of at least n ; x + 1 b oundary p oints of A from the right of the square to just b elow x , and these paths do not intersect. Therefore  ( k  ' L n )= @ in A  2 n ; x ; y +2  r +1 : If r < n then  ( k ' D L n ) = r +1   ( k ' L n ), while if r  n then  ( k ' D L n )  n   ( k ' L n ). Thus in this case wehave the inequality claimed. Finally, consider the case when only one of the the corners ( n 1) and (1 n )isin A .In these cases wehave @ in A = n   ( k ' D L n ). The previous Prop osition is a sp ecial case of Corollary 9 in 2], who in fact prove the d -dimensional version for arbitrary d . We b elieve our pro of for d = 2 is of interest by itself. 5 Theorem 1. For any n , ' D is optimal for the VertSep , MinSumCut and MinVertBis problems on ( L n ). Moreover, minvs ( L n ) = minvb ( L n ) = n and n ; 3 minsc ( L n ) ! 2 = 3as n !1 . Proof. The previous isop erimetric inequality yields the optimality of ' D for the costs of minvs , minsc and minvb on L n .Also we get that minvs ( L n ) = minvb ( L n ) = n . To compute the sum of the cuts for ' D , consider for eachpoint in the lattice the value of the vertex cut pro duced by the diagonal ordering (see Figure 1), then arranging the sum by points with the same vertex cut, weget minsc ( L n )= n X i =1 n X j =1 j + n X i =3 i ( i ; 2) + ( n ; 1) X i =2 i = 2 3 n 3 + 1 2 n 2 ; 7 6 n: Lemma 1. For any lattice graph L with n vertices, and any m 2 f 1  2 ::: n g , there is a layout ' on L such that  ( m ' L )  2 3 = 2 p n +1. Proof. We are lo oking for a subset S of L consisting of m vertices, suchthat there are at most 2 3 = 2 p n + 1 edges b etween S and L n S . Let > 0 b e a constant, to b e chosen later. For x 2 Z let S x = f y 2 Z :( x y ) 2 L g and let V = f x 2 Z : j S x j  p n g . For i 2 Z ,let H i denote the half-space ( ;1 i ]  R . Set i 0 =min f i 2 Z : j L \ H i j m g : Consider the case i 0 = 2 V . Then dene S to b e a set of the form S = L \ ( H i 0 ; 1  ( f i 0 g ( ;1 j ])) with j chosen so that S has precisely m elements. With this denition of S for i 0 = 2 V ,the number of horizontal edges between S and L n S is at most j S i 0 j , and hence is at most  p n . There is at most one vertical edge b etween S and L n S , so the numb er of edges from S to L n S is at most  p n +1 when i 0 = 2 V . Now consider the other case i 0 2 V .Let I = i 1 i 2 ] b e the largest integer interval which includes i 0 and is contained in V .Then i 1 ; 1 = 2 V ,and i 2 +1 = 2 V .Also, as j V j  ; 1 p n , i 2 ; i 1 +1   ; 1 p n . Wehave j L \ H i 1 ; 1 j <m j L \ H i 2 j : For j 2 Z let T j = i 1 i 2 ]  ( ;1 j ]. Cho ose j 0 so that j L \ ( H i 1 ; 1  T j 0 ; 1 ) j <m j L \ ( H i 1 ; 1  T j 0 ) j  6 and let S be L \ ( H i 1 ; 1  T j 0 ; 1  ( i 1 i 3 ] f j 0 g ))  with i 3 2  i 1 i 2 ] chosen so that S has precisely m elements. We estimate the number of edges between S and L n S for the case i 0 2 V .Since i 1 ; 1 = 2 V ,and i 2 +1 = 2 V , the number of horizontal edges between S and L n S is at most 2  p n +1. Also, since i 2 ; i 1 +1   ; 1 p n , the number of vertical edges b etween S and L n S is at most  ; 1 p n .Combining these estimates we nd that there are at most (2  +  ; 1 ) p n +1 edges b etween S and L n S , whether or not i 0 2 V . The minimum value of 2  +  ; 1 (achieved at  =2 ; 1 = 2 )is2 p 2. Setting  =2 ; 1 = 2 in the ab ove denition, wehave the partition required. Using Lemma 1, taking m = b n= 2 c and the fact that minvb ( L )  minbis ( L ), we get the following result. Theorem 2. For any lattice graph L with n vertices minbis ( L )  2 3 = 2 p n +1 and minvb ( L )  2 3 = 2 p n +1. For the MinCut problem the b ound changes in the constant, Theorem 3. For any lattice graph L with n vertices, mincut ( L )  14 p n . Proof. First supp ose we have n = 2 m for an integer m . The pro of is based on recursive bisection, with the cut size guaranteed by Lemma 1. Let f ( m ) denote the maximum mincut cost of all lattice graphs with 2 m vertices then f ( m ) satises the following recurrence: f ( m )  ( 0 if m =0  2 3 = 2 2 m= 2 +1+ f ( m ; 1) otherwise : Then, solving the recurrence, weget f ( m )  m X j =1 (2 3 = 2 2 j= 2 +1) = 4(2 1 = 2 +1)(2 m= 2 ; 1) + m: We can drop the assumption that n = 2 m , by taking m so that n  2 m < 2 n ,and adding extra p oints until one has a set of size 2 m . By monotonicity this pro cess do es not reduce the mincut cost, so mincut ( L )  2 5 = 2 (2 1 = 2 +1) p n + (log 2 ( n )+1) ; 4(2 1 = 2 +1)  13 : 657 p n +log 2 ( n ) ; 8 : But notice that for any x> 0wehave (log 2 ( x ) ; 8) = p x< 0 : 067 therefore the ab ove b ound for mincut ( L ) is at most 14 p n for all n . 7 As a consequence of the previous theorem, and the fact that for any graph G , minla ( G )  n mincut ( G ), minsc ( G )  n minvs ( G ), and minvs ( G )  mincut ( G ), we can extend the previous result to the remaining problems. Corollary 1. For any lattice graph L with n vertices, minvs ( L )  14 p n , minla ( L )  14 n p n and minsc ( L )  14 n p n . In the case of the full square lattice graphs with side n , the ab ove upp er b ounds are within a constant of their optimal costs. 3 Convergence results for random lattice graphs Let us describ e some basic concepts of site p ercolation for the lattice L m with vertex set V m =(0 m ) \ Z ) 2 .Given p 2 (0  1), site percolation with parameter p on L m is obtained by taking a random set of open vertices of V m with each vertex b eing op en with probability p indep endently of the others. Let L mp be the subgraph of L m obtained by taking all edges between op en vertices. Wesay that L mp is a random lattice graph . Denote Pr p and E p the probability and exp ectation with resp ect to the describ ed pro cess of site p ercolation with parameter p . By a cluster we mean the set of vertices in any connected comp onentof L mp . Let e C 0 denote the cluster in L mp that includes (0  0) (p ossibly the emptyset) and let e C x denote the cluster in L mp that includes the p oint x . A similar site p ercolation pro cess can be generated analogously on the innite lattice with vertex set Z 2 and edges b etween nearest neighb ors. In the same waywe can extend Pr p and E p to this innite pro cess. Let us denote by C 0 the cluster including the origin for site p ercolation on Z 2 .It may b e the case that C 0 is empty. Notice that we can view the random lattice graph as generated by a site p ercolation pro cess on Z 2 and taking the op en vertices in V m . In this section we consider random lattice graphs generated by subcritical limiting regimes ( p<p c ), in which all clusters in the innite pro cess are almost surely nite. W ebegin by giving b ounds for the MinCut and VertSep problems on the sub critical p ercolation pro cess on the lattice L m . Theorem 4. Assume 0 <p<p c , there exists constants 0 <c 1 <c 2 suchthat lim m !1 Pr  c 1  minvs ( L mp ) p log m  mincut ( L mp ) p log m  c 2  =1 : Proof. Recall that for any graph G , minvs ( G )  mincut ( G ). The mincut of a disconnected graph is the maximum of the mincut s of its connected comp onents. Hence, for any p ositive constant c 2 , Pr h mincut ( L mp )  c 2 p log m i = Pr h  x 2 V m n mincut ( e C x )  c 2 p log m oi 8 By the site p ercolation version of Equation 5.7 in 6], there exists > 0 such that Pr  j C 0 j n ]  e ; n . Therefore by Theorem 3 Pr h mincut ( L mp )  c 2 p log m i  Pr h  x 2 V m fj e C x j ( c 2 = 14) 2 log m g i  m 2 exp( ;  ( c 2 = 14) 2 log m ) : Cho osing c 2 > 14 p 2 = we get Pr  mincut ( L mp )  c 2 p log m  ! 0. To get a lower b ound for minvs ( L mp ), let  > 0and let T 1 ::: T j ( m ) be disjoint lattice subsquares of L m , each of side b (  log m ) 1 = 2 c , where j ( m )= b m= b (  log m ) 1 = 2 cc 2 : Set  =log(1 =p ) so that p = e ;  . Let A j be the eventthat all sites in T j are op en. Then Pr  A j ] = exp( ;  b (  log m ) 1 = 2 c 2 )  m ;  : Hence, Pr h \ j ( m ) i =1 A c i i  (1 ; m ;  ) j ( m )  exp( ; m ;  j ( m )) , which tends to zero provided  is chosen so that  < 2. As minvs ( L m )= m by Theorem 1, weget  j ( m ) i =1 A j f minvs ( L mp )  (  log m ) 1 = 2 g : Taking c 1 = p  we obtain the lower b ound. Notice that the ab ove theorem only gives an order of magnitude result for the minimal cost and wedonot have a convergence result. The order of magnitude is ( p log m ), which contrasts with the sup ercritical case p > p c ,for which minvs ( L mp ) and mincut ( L mp ) are ( m )13]. In the next lemma weprove that for sub critical site p ercolation with parameter p , the exp ected ratio of the minla ( C 0 )and j C 0 j is nite. We also give a similar result for the MinSumCut problem. Tocover the case C 0 =  ,weusetheconvention 0 = 0 = 0, throughout the remainder of the pap er. Lemma 2. For any p 2 (0 p c ), E p  minla ( C 0 ) j C 0 j  2 (0  1 )and E p  minsc ( C 0 ) j C 0 j  2 (0  1 ) : Proof. Let R 0 = min f n : C 0   ; n n ] 2 g then by considering the lexicographic ordering of vertices one sees that minsc ( L m )  m 3 and minla ( L m )  m 3 ,which together with monotonicity gives us that minsc ( C 0 )  (2 R 0 +1) 3 and minla ( C 0 )  (2 R 0 +1) 3 . The statement of the lemma follows from the fact that Pr p  R 0 > n ]decays exp onentially in n (again, see chapter 5 of 6]). We use this lemma to state one of our main results, namely that the value of minla on random lattices, divided by m 2 , converges in probability to a constant. Recall (see for example 9 F L n L L mp G ( X n  r n ) minbis F = n +(odd n ) 7] F  2 p 2 n +1 F Pr ;! 0 F Pr ;! 0 minvb F = n F  2 p 2 n +1 F Pr ;! 0 F Pr ;! 0 mincut F = n +(odd n ) 7] F  14 p n c 1  F= p log m  c 2 whp minvs F = n F  14 p n c 1  F= p log m  c 2 whp minla F =(4 ; p 2) n 3 = 3+ o ( n 3 )8  9] F  14 n p nF=m 2 Pr ;!  LA F=n Pr ;! ~  LA ( d ) minsc F =2 n 3 = 3+ o ( n 3 ) F  14 n p nF=m 2 Pr ;!  SC F=n Pr ;! ~  SC ( d ) Table 1: Summary of results for full n  n square lattice graphs ( L n ), general lattice graphs with n no des ( L ), random lattice graphs in m  m lattices with probability p ( L mp ), and random geometric graphs with n no des and radius r n where lim nr d n =  ( G ( X n  r n )). In the rst tworows we require that p<p 0 c and < 0 c . For the remaining rows p<p c and < c . 16 References 1] J. Beardwo o d, J. Halton, and J.M. Hammersley. The shortest path through many p oints. Proceedings of the Cambridge Philos. Society. , 55:299{327, 1959. 2] B. Bollobas and I. Leader. Compressions and isop erimetric inequalities. Journal of Combinatorial Theory Series A , 56:47{62, 1991. 3] K.L. Chung. A Course in Probability Theory . Academic Press, New York, 1974. 4] J. D !az, M. D. Penrose, J. Petit, and M. Serna. Linear orderings of random geometric graphs. Technical rep ort, Departament de Llenguatges i Sistemes Inform"atics, UPC, http://www.lsi.up c.es/  jp etit/Publications , 1999. 5] N. Dunford and J. Schwartz. Linear Op erators. Part I: General Theory. Interscience Publisher., New York, 1958. 6] G. Grimmett. Percolation. (2nd edition) . Springer-Verlag, Heidelb erg, 1999. 7] F.T. Leighton. Introduction to Paral lel Algorithms and Architectures: Arrays, Trees, Hypercubes . Morgan Kaufmann, San Mateo, CA., 1993. 8] G. Mitchison and R. Durbin. Optimal numb erings of an n  n array. SIAM Journal on Discrete Mathematics , 7(4):571{582, 1986. 9] D.O. Muradyan and T.E. Pilip osjan. Minimal numb erings of vertices of arectangular lattice. Akad. Nauk. Armjan. SRR , 1(70):21{27, 1980. In Russian. 10] K. Nakano. Linear layouts of generalized hyp ercub es. In J. van Leewen, editor, Graphtheoretic concepts in computer science ,volume 790 of Lecture Notes in Computer Science , pages 364{375. Springer-Verlag, 1993. 11] C. H. Papadimitriou and M. Sideri. The bisection width of grid graphs. In First ACMSIAM Symp. on Discrete Algorithms. , pages 405{410, San Francisco, 1990. 12] M. Penrose. Single linkage clustering and continuum p ercolation. Journal of Multivariate Analysis. , 53:94{109, 1995. 13] M.D. Penrose. Vertex ordering and partition problems for random spatial graphs. Technical rep ort, University of Durham, 1999. 14] J.M. Steele. Probability theory and Combinatorial Optimization .SIAM CBMS-NSF Regional Conference Series in Applied Mathematics., 1997. 17 15] J.E. Yukich. Probability Theory of classical Euclidian Optimization Problems. Springer{ Verlag, Heidelb erg, 1998. 18