Light Orthogonal Networks with Constant Geometric Dilation

Light Orthogonal Networks with Constant Geometric Dilation

Adrian Dumitrescu Csaba D.T′o th

December30,2006

Abstract

An orthogonal network for a given set of points in the plane is an axis-aligned planar straight line graph that connects all input points.We show that for any set of points in the plane,there is an

orthogonal network that(i)is short having a total edge length of,where denotes the length

of a minimum Euclidean spanning tree for the point set;(ii)is small having vertices and edges;

and(iii)has constant geometric dilation,which means that for any two points and in the network,

the shortest path in the network between and is at most constant times longer than the(Euclidean)

distance between and.

1Introduction

A typical problem in the theory of metric embeddings asks for a mapping from one metric space to another that distorts the distances between point pairs as little as possible.In this paper,we address the following problem about geometric dilation:Given a?nite set of points in the plane,?nd a small plane graph containing so that the distortion between the distance and the Euclidean shortest path distance between any two points(on edges or at vertices)of is bounded by a constant.

A special case of this problem received frantic attention in the late80s and early90s in the context of geometric spanners[6,8,16,18](see[14]for a survey).One of the latest results,due to Bose et al.[5], goes as follows:For any set of points in the plane,there is a plane graph with four properties: (i)the vertex set of is,(ii)has maximum degree,(iii)the total length of the edges of is

,where is the length of the minimum Euclidean spanning tree for,and(iv)for any two vertices the(Euclidean)shortest path along is at most times longer than the distance between and.The last property is also referred to as constant vertex-dilation.Note that the graph

is sparse and the bound is the best possible,since has to be connected at least.Intuitively,this graph corresponds to a road network that has constant detour(precise de?nition is below)between any two of given cities.However,there may be pairs of points along the roads(halfway between cities)with arbitrarily large detour.In the current paper,we further extend the results in[5]and construct a graph of constant geometric dilation,that is,constant detour between any two points of the graph(not just between vertices).

Let us?rst de?ne the(geometric)dilation formally(see also[11,12]).Let be an embedded planar graph whose edges are curves.Let also denote the set of points covered by the edges and vertices of the embedded graph.The detour between two points(on edges or vertices of)is the ratio between the length of a Euclidean shortest path connecting and in and their Euclidean

distance.The supremum value of detours over all pairs of points,denoted,is called the geometric dilation of:

;Dobkin et al.[10]gave a constant bound on vertex-dilation of the Euclidean Delaunay triangulation.Das and Joseph[8]found a large class of geometric graphs with this property,characterized by a certain diamond property similar to our concept of lofty PLSGs(see Def.1).A lot of work has been done on?nding”good”spanners:sparse and light graphs with constant vertex-dilation.Quite a few papers[1,3,6,18]present algorithms that compute,for a set of points in the plane,a graph with vertex set that has constant vertex-dilation,edges,and length.Das et al.[9] generalized the result to-space.Some of these algorithms run in time,some compute graphs that are planar or have bounded maximal degree.Recently,Bose et al.[5]were able to combine all these properties.However,none of these papers provide any upper bound on the resulting geometric dilation. Aronov et al.[2]gave a tight worst-case bound on the vertex-dilation in terms of the number of edges of the graph used to connect points.

Geometric dilation of planar point sets.The problem of embedding a given planar point set in a network of small geometric dilation,as well as the problem of computing or estimating the dilation of planar net-works has only recently received attention.First attempts were made in designing ef?cient algorithms to compute the dilation of a polygonal curve[13,17].Ebbers-Baumann et al.[12]proved that every?nite point set can be embedded in a plane graph(with curved edges)of geometric dilation at most1.678,and Du-mitrescu et al.[11]showed that some point sets require geometric dilation strictly more than: at least,to be precise.

Related problems.A somewhat related problem is the Manhattan network problem.A plane graph whose vertex-dilation is1under the metric is called a Manhattan network[4,15].For our purpose such networks might be too expensive:Take,for instance,equidistant points on the boundary of an axis-aligned unit square;the minimum Manhattan network is times longer than the MST,and it contains Steiner vertices;while the unit square itself has length,vertices,and geometric dilation2.

2Reduction to axis-aligned polygons

Notation on planar straight line graphs and polygons.A planar straight line graph (P SLG )is a ?nite graph together with a planar embedding,where the vertices are distinct points and the edges are straight line segments,any pair of which being either disjoint or having a common endpoint.The complement of a P SLG may have several components,which are the faces of .Since is ?nite,exactly one face extends to in?nity,while all other faces are bounded .The portion of that lies on the boundary of a face is the P SLG .If is a simply connected region,then the P SLG is a weakly simple polygon ,for convenience called polygon in this paper.A polygon and its interior jointly form the polygonal domain

.A subdivision of a polygon is a P SLG with .

The length of a P SLG ,denoted

,is the total length of the edges of .The perimeter of a (weakly simple)polygon is the length of a shortest closed path that visits all vertices of along the boundary.

Since this closed path can traverse some edges twice,the perimeter of is less than

.2.1Our algorithm in a nutshell

We construct an orthogonal network for a given set of points in the plane (Fig.1(a)).First,we reduce the problem to a polygon subdivision problem.We construct a constant factor approximation of a

minimum axis-aligned Steiner tree (MAST)of .

retains a key property of a MAST,which we call loftiness .Intuitively,a P SLG is lofty if nearby parallel edges do not form ”narrow channels.”Such narrow channels are undesirable because the detour between closest points on opposite sides of a channel is too large.We enclose in an appropriate axis-aligned bounding square ,add a segment connecting and and thus obtain a lofty weakly simple polygon (Fig.1(b)).It suf?ces to subdivide into polygonal faces of constant geometric dilation such that the total length and the number of vertices increase by at most constant

factors.

(a)(b)(c)

(d)

Figure 1:The three main steps of our algorithm.(a)A point set;(b)a rectilinear Steiner tree

and a bounding square ;(c)a mountain subdivision;and (d)a re?ned subdivision into polygons of constant geometric dilation.We augment with new edges and vertices in two phases.The ?rst phase decomposes a lofty axis-aligned polygon into lofty pocketed mountain polygons;see Def.3and Fig.1(c).The advantage of moun-tains is that it is easy to approximate their dilation in terms of the detours of horizontal and vertical point pairs (see Lemma 2).In the second phase,we greedily decompose each pocketed mountain polygon into pocketed mountains of constant dilation in a top-down sweepline algorithm:Whenever the portion of a mountain above the sweepline has ”critical”vertical or horizontal dilation,we insert new edges that sepa-rate this area and an adjacent buffer zone from the rest of the mountain (Fig.1(d)).The buffer zones serve

to make sure that the detour is bounded by a constant for points lying on the newly inserted edges.

2.2Reduction to axis-aligned subdivisions

Let be a polygon.The internal dilation of is over all point pairs

such that the line segment lies in.To prove a constant bound on the geometric dilation in Theorem1part(i),it will suf?ce to bound the internal dilation of all polygonal faces of the?nal network. For this,recall a result of Ebbers-Baumann et al.[12]which says that the dilation of a plane graph is attained for a pair of visible points(where but the relative interior of the segment is disjoint from).In our?nal graph,any pair of visible points lie on the boundary of a bounded(polygonal)face of.Thus if the internal dilation of every bounded face is at most,then the dilation of is also at most .

Theorem2For every set of points in the plane,there is an axis-aligned subdivision of a bounding square of such that(i)the internal dilation of every bounded face of is at most;(ii)has at most vertices;and(iii).

It is now easy to see that Theorem1follows from Theorem2,since conditions(ii)and(iii)are the same.

2.3Reduction to lofty axis-aligned polygons

Given a set of points in the plane,we?rst construct a Steiner spanning tree with.Ideally, should be the minimum axis-aligned Steiner tree(MAST)of,which has at most vertices and whose length is at most

length,and is2-lofty as de?ned below.

De?nition1Given an axis-aligned P SLG and a parameter,a-narrow channel is an axis-aligned rectangle of aspect ratio at least such that(a)the two longer sides of are contained in two parallel edges of(but neither of these sides contains any vertex of);(b)the interior of is disjoint from.(See Fig.2(a).)

An axis-aligned P SLG is-lofty,for,if it does not admit any-narrow channel.

By de?nition,if,and is-lofty,then it is also-lofty.Note that a MAST is-lofty for any:If there were a-narrow channel with for an MAST,then one can construct a shorter axis-aligned Steiner tree by replacing a portion along a longer side of with the two shorter sides of (see Fig.2(a-b)).

It is not dif?cult to devise a constant-factor approximation to the MAST that is also2-lofty.Start with an arbitrary input point and let be a singleton graph.For every, construct an axis-aligned Steiner tree on points of by extending.If is available,compute the minimum distance from to remaining points and connect to a closest point using at most two axis-parallel edges(forming an L-shape)and at most one Steiner point(the closest point in or the joint of the L-shape).By Prim’s result[20],the axis-parallel Steiner tree is not longer than the minimum rectilinear spanning tree(which has no Steiner points but the edge length is measured in norm);which in turn is at most

(a)(b)

(c)

Figure 2:(a-b)If an axis-aligned Steiner tree

is not 2-lofty,then it is not minimal.(c)This argument does not work if the two longer sides of contains some vertices of .

Let be the minimum axis-aligned bounding box of ,and let be a bounding square of of side

length

which extends by at least in each direction.Let now be the P SLG formed by the union of ,,and an axis-parallel segment connecting a vertex of

on to the closest point in .Note that is also 2-lofty,and we have .(The perimeter of ,however,is at most

Our algorithm is a modi?ed version of a standard algorithm that subdivides an axis-aligned polygon into mountains.For completeness,we ?rst present this standard algorithm.Its input is and a base edge .

Rotate to make horizontal.Let be the boundary polygon of the set of all points

for which such that is vertical and .Clearly,is a

mountain.If ,then decomposes into and other faces,each of which has a

unique edge that is adjacent to

but is not contained in edges of .Recurse on each face,except for

,independently,setting the base to be the edge adjacent to .(See Fig.3.)(a)(b)(c)

(d)(e)

Figure 3:The progress of the standard subdivision algorithm into mountains.

Unfortunately this standard subdivision scheme may produce mountains that are not 3-lofty.

A narrow channel may be located either outside of

along a vertical edge of ,or in between two vertical edges of .To eliminate all narrow channels,we extend the faces of

the graph to ?ll adjacent narrow channels.Intuitively,we attach ”pockets”to the mountains.

De?nition 3(see Fig.4)A vertical (horizontal)pocketed mountain is a polygon obtained from a vertical

(horizontal)mountain

by replacing some segments along by a 3-path such that forms a rectangle (a pocket )lying outside

,where the side of orthogonal to has length at most

.Figure 4:A mountain polygon (left)and a pocketed mountain polygon (right).

Lemma 1Every axis-aligned 3-lofty polygon

with vertices admits an orthogonal subdivision ,

where:every face of is a 3-lofty pocketed mountain;;and has at most vertices.

Proof.We describe a recursive algorithm,whose input is a polygon and a base segment contained in ,which computes a subdivision of into3-lofty pocketed mountains.Initially is an arbitrary horizontal edge of.Let be the boundary polygon of the set of all points for which such that is vertical and.See Fig.5(a-b)).The graph is a subdivision of,in which is a face.If,then the algorithm terminates,otherwise it modi?es in several steps to eliminate all-narrow channels,.The main tool is the following pocketing subroutine,which extends a face of by attaching to it adjacent narrow channels.

pocketing(see Fig.5).Input:A P SLG and a face.

As long as has a-narrow channel not contained in with and one of its long

sides lying along,do:

Let be such a narrow channel with maximal.Let be the rectangle obtained from by

removing two rectangles of aspect ratio2along its top and bottom sides.Delete the long side

of that lies along and insert the two short sides of into.

base b

(a)(b)(c)

(d)(e)(f)

Figure5:(a)A polygon with a(pocketed)base.(b)The polygon is adjacent to a narrow channel.

(c)Subroutine pocketing extends to a polygon.(d)The base of every face in is the vertical edge adjacent to.(e)Narrow channels and in.(f)Subroutines pocketing

and pocketing splits into several polygons.

Apply pocketing(see Fig.5(b-c)).Since is3-lofty,any narrow channel of in the exterior of must lie between a vertical edge of and a vertical edge of.Note that the

pockets are disjoint.Each step of the pocketing subroutine adds at most four new vertices(the four corners of)and two new edges(the two horizontal sides of).The removal of two small rectangles from along its horizontal sides guarantees that the new horizontal edges do not form3-narrow channels with any other edge.

Let denote the face of the resulting subdivision that contains(that is,contains and some adjacent pockets).Denote by the set of all faces of except for.In each face,choose a base,which is the unique edge adjacent to but not contained in (Fig.5(d)).Apply subroutine pocketing for every successively(Fig.5(e-f)).This

destroys narrow channels lying in by attaching pockets to the base sides of the faces in. It may also split the face into several faces:Let denote the polygon(s)obtained from after this procedure.The graph is a subdivision of polygon into faces,where the faces of are pocketed mountains,and every base of other faces may have pockets attached.Apply this subdivision algorithm recursively with input for every face,independently.This completes the description of the algorithm.

Charging scheme for length:We charge every edge created by our algorithm to a portion of the perimeter of.Recall that each step of the pocketing subroutines removes a long side of a rectangle of aspect ratio at least2and inserts its two short sides.Clearly,this operation does not increase the length of the graph.Assume that the edge set of is.Let be the set of new edges constructed when building polygons for all bases in our algorithm.It is enough to charge the total length of edges in to the perimeter of.Consider a step where the base is horizontal,and the mountain extends vertically above.Charge the length of each edge to the portion of the perimeter of that is horizontally visible from,and has the same length as.(Note that the shorter edges of rectangles arising in pocketing subroutines are never charged.)Every point along the perimeter is charged at most once.Hence,.

Charging scheme for vertices:We count the number vertices created during the decomposition of polygon with vertices.Every edge in is incident to a re?ex vertex of;and every re?ex vertex is incident to at most one edge of because if is incident to a new edge of some mountain ,then becomes a convex vertex in the recursive steps.Hence,we have.Each edge of

is incident to a vertex of and a potentially new vertex,so the construction of polygons increases the number of vertices by.Each step of the pocketing subroutines increases the number of vertices by 4(the corners of a rectangle).Next,we deduce an upper bound on the number of these steps.First consider the pockets created in subroutines pocketing for all bases.Every such pocket lies between an edge of and a parallel edge of,and every pair of parallel edges in corresponds to at most one pocket.If we draw a curve in each pocket that connects the two corresponding edges of and,we obtain a planar bipartite graph on vertex set,which has less than

edges by Euler’s polyhedron theorem.Since,the number of pockets is less than.These pockets also split some edges of into several pieces;denote the set of these pieces by .Each pocket partitions an edge of into two pieces,so we have.Now consider the pockets created in subroutines pocketing for all.Each such pocket lies between an edge of and a parallel edge of.By a similar argument,the number of these pockets is at most.The subdivision of the input polygon has at most

vertices.

3.2Subdividing lofty mountains into polygons of constant geometric dilation

In this subsection,we present an algorithm to subdivide a3-lofty mountain polygon into polygons of con-stant internal dilation.We extend this algorithm in the next subsection to3-lofty pocketed mountains.The

advantage of using mountains is that one can approximate their internal dilation in terms of special detours of axis-parallel segments.Consider a mountain with a horizontal base side .For every horizontal

segment

that lies in the polygonal domain and ,we denote by the length of the (upper)arc between and along the perimeter of that does not contain the base side.Lemma 2The internal dilation of every vertical mountain

is upper bounded by ,where

over all horizontal ,with ;

,where is the shortest vertical segment with endpoints on and

whose interior lies in .Proof.Consider two points for which the internal dilation of is attained.That is,

is maximal over all segments that lie in the polygonal domain and .We distinguish two cases:(1)either or lies in the base side,(2)neither nor lies in the base side.

(a)

(b)

(c)

Figure 6:(a-b)Approximating the internal dilation of a mountain in two cases.(c)For and -and -monotone axis-aligned polygon ,the internal dilation can be arbitrarily large even though and are bounded.

If ,then

and so is at least as long as .Since is less than ,we have .Assume that .Denote by (resp.,)the length of the horizontal

(resp.,vertical)component of segment .Let

be the staircase path between and whose vertical segments all lie in

(see Fig.6).Clearly,we have .The graph distance is at most the sum of the graph distances of the portions of ,and for every portion above a horizontal

segment ,it is .Hence,.Note that the internal dilation of arbitrary axis-aligned polygons cannot be bounded in terms of detours

of only horizontal and vertical point pairs.Fig.6(c)shows that an -and -monotone polygon

can have arbitrarily large dilation even though the ratio is at most 3for any horizontal or vertical segment .

In the remainder of this subsection,we present and analyze an algorithm for subdividing 3-lofty moun-tains into axis-aligned polygons with constant internal dilation.Our algorithm greedily chooses polygons for which the dilation bound of Lemma 2is above a constant threshold.We prove the following.

Lemma 3Every 3-lofty mountain

with vertices admits an orthogonal subdivision ,where:the internal dilation of every face of is at most 45;;and has at most vertices.

Proof.We are given a vertical mountain that lies above the -axis,with the base side on the -axis.For every horizontal segment ,we de?ne a padding ,which is a rectangle of aspect ratio 3whose top

longer side is .Perturb the -coordinates of horizontal edge of

by a tiny ,if necessary,so that no two horizontal edges of are collinear.This simpli?es our notation when we scan in a sweep-line

algorithm.Let denote the set of maximal horizontal segments

where and .We subdivide

recursively into 3-lofty mountains as follows.Move a horizontal sweep line from the top of down,and scan the segments of

lying

along .We subdivide if either of the following two events occurs.1.If the padding of the segment

intersects the base side ,then insert two vertical edges connecting and to the base side,and apply the pocketing subroutine to the face

containing .

2.If ,then insert the lower,left,and right edges of the padding of

,and

apply the pocketing subroutine to the face containing .Recurse on each face of the resulting subdivision of

that lies in the closed halfplane below

.An illustration of the subdivision algorithm is shown in Fig.7.

(a)(b)(c)?

u v (d)(e)

(f)

Figure 7:The progress of our subdivision algorithm for mountain polygons.

Analysis.We show ?rst that every face in the resulting subdivision of has bounded dilation.Initially,

when the sweep line passes through the top horizontal edge of ,we have

.The ratio increases while and move along vertical edges of ,and it does not increase when reaches a horizontal edge of .The padding of moves continuously with the sweep line while and move along vertical edges of ,but the padding may increase dramatically when reaches a

horizontal edge of .Let us consider the case that passes through segments two visibility ,,and

a horizontal edge.(Segment is a single edge of,since no two edges of are collinear.) The paddings of and are disjoint from,and the padding of the edge is also disjoint from, since is3-lofty.Therefore,if the padding of intersects,then the distance of and is at least

.

Assume that step1is applied.Denote by the(mountain)polygon between the vertical segments incident to and;and let be the polygon obtained from by pocketing.The perimeter of is at most .The pocketing subroutine can increase the length of the new edges by a factor of at most

and with pockets.We next give an upper bound on.If does not contain any horizontal edge of,then the length of is at least,the height of the padding of.If contains a horizontal edge of,then the length of is at least.Hence,

.

Next assume that step2is applied.Denote by,the(mountain)polygon formed by three sides of and the portion of above;and let be the polygon obtained from by pocketing.The perimeter of is at most

long new perimeter is created along the faces of.If step2is applied,then at least portion of the perimeter of is discarded,and at most

3.3Subdividing lofty pocketed mountains into polygons of constant geometric dilation

In Subsection3.1,we have subdivided a polygon into pocketed mountains,and in Subsection3.2we have subdivided mountains into polygons of constant dilation.It remains to show how to subdivide a pocketed mountain.

Lemma4Every3-lofty pocketed mountain with vertices admits an orthogonal subdivision,where: the internal dilation of every face of is at most75;;and has at most vertices. Proof.We are given a pocketed mountain with vertices corresponding to a mountain and a set of disjoint pockets(see Def.3).Recall that each pocket has a common side with,and its sides orthogonal to have length at most.Note also that is shorter and has fewer vertices than.

Subdivide into polygons of bounded dilation as described in Subsection3.2,and let be the result-ing network.Run the pocketing subroutine for the graph and each face of(Subsection3.1).This may attach all or some portions of each pocket to faces of.Consider a maximal portion of a pocket that has not been attached to any face of.If the aspect ratio of is at most3,then it is a rectangular face of dilation at most4.If the aspect ratio of is,then must have at least vertices along. Subdivide by segments orthogonal to into rectangles of aspect ratio at most3.In this step,the

number of vertices is at most doubled,and the length of increases by at most a factor of

;and it can also increase the dilation by at most the same factor.

4Conclusion

We have shown that any set of points in the plane can be embedded in a planar network with geometric dilation,has vertices,and length.In addition,we also guaranteed that all edges are axis-parallel(orthogonal network),so the maximum degree is4.Some questions remain open.The constants hidden in the asymptotic notation are at the moment prohibitively large for practical applications. An obvious question is to improve the constants to a level close to that of low vertex-dilation networks. We do not know if Steiner points are necessary(if the edges are not required to be axis-parallel).Another natural question is whether it is possible to construct a network with the additional property that all bounded faces are convex(e.g.,all bounded faces are rectangles in case of an orthogonal network).We conjecture the answer to be negative.Speci?cally,we suspect that a set of points uniformly distributed on two concentric circles of radii1and2has the property that every network with vertices,length, and dilation must have a nonconvex bounded face.

Acknowledgments.We thank Ansgar Gr¨u ne and Minghui Jiang for interesting discussions on the topic. We are also grateful to an anonymous reviewer for several useful comments and observations.

References

[1]I.Alth¨o fer,G.Das,D.P.Dobkin,D.Joseph,and J.Soares,On sparse spanners of weighted graphs,

Discrete Comput.Geom.9(1993),81-100.

[2]B.Aronov,M de Berg,O.Cheong,J.Gudmundsson,H.J.Haverkort,and A.Vigneron,Sparse geo-

metric graphs with small dilation,in Proc.16th ISAAC,vol.3827of LNCS,Springer,2005,pp.50–59.

[3]S.Arya,G.Das,D.M.Mount,J.S.Salowe,and M.Smid,Euclidean spanners:short,thin,and lanky,

in Proc.27th STOC,1995,ACM Press,pp.489-498.

[4]M.Benkert,A.Wolff,F.Widmann,and T.Shirabe,The minimum Manhattan network problem:

approximations and exact solutions,Comput.Geom.Theory Appl.35(2006),188–208.

[5]P.Bose,J.Gudmundsson,and M.Smid,Constructing plane spanners of bounded degree and low

weight,Algorithmica42(2005),249–264.

[6]B.Chandra,G.Das,G.Narasimhan,J.Soares,New sparseness results on graph spanners,Int.J.

Comput.Geometry Appl.5(1995),125–144.

[7]L.P.Chew,There are planar graphs almost as good as the complete graph,https://www.wendangku.net/doc/485494428.html,puter Sys.Sci.39

(1989),205-219.

[8]G.Das and D.Joseph,Which triangulations approximate the complete graph?in Proc.Int.Symp.on

Optimal Algorithms,vol401of LNCS,Springer,1989,pp.168–192.

[9]G.Das,G.Narasimhan,and J.S.Salowe,A new way to weigh malnourished Euclidean graphs,in

Proc.6th SODA,ACM Press,1995,pp.215–222.

[10]D.P.Dobkin,S.J.Friedman,and K.J.Supowit,Delaunay graphs are almost as good as complete

graphs,Discrete Comput.Geom.5(1990),399-407.

[11]A.Dumitrescu,A.Ebbers-Baumann,A.Gr¨u ne,R.Klein,and G.Rote,On the geometric dilation of

closed curves,graphs,and point sets,Comput.Geom.Theory Appl.362006,16–38.

[12]A.Ebbers-Baumann,A.Gr¨u ne,and R.Klein,On the geometric dilation of?nite point sets,Algorith-

mica44(2006),137–149.

[13]A.Ebbers-Baumann,R.Klein,https://www.wendangku.net/doc/485494428.html,ngetepe,A.Lingas,A fast algorithm for approximating the detour

of a polygonal chain,Comput.Geom.Theory Appl.27(2004),123–134.

[14]D.Eppstein,Spanning trees and spanners,in Handbook of Computational Geometry(J.R.Sack and

J.Urrutia,eds),North-Holland,Amsterdam,2000,pp.425–461.

[15]J.Gudmundsson,C.Levcopoulos,and G.Narasimhan,Approximating a minimum Manhattan net-

work,Nordic J.of Computing8(2001),216–229.

[16]M.Keil and C.A.Gutwin,Classes of graphs which approximate the complete Euclidean graph,

Discrete Comput.Geom.7(1992),13–28.

[17]https://www.wendangku.net/doc/485494428.html,ngerman,P.Morin,and M.Soss,Computing the maximum detour and spanning ratio of planar

chains,trees and cycles,in Proc.19th STACS,vol.2285of LNCS,Springer,2002,pp250–261. [18]C.Levcopoulos and A.Lingas,There are planar graphs almost as good as the complete graphs and

almost as cheap as minimum spanning trees,Algorithmica8(1992),251–256.

[19]J.MacGregor Smith&P.Winter,Computing in Euclidean geometry,in Computational Geometry and

Topological Network Design,World Scienti?c,1992,pp.287–385.

[20]R.C.Prim,Shortest connection networks and some generalizations,Bell System Technical Journal

36(1957),1389–1401.