Geometric tree graphs of points in convex position

DISCRETE APPLIED ELSEYIER Discrete Applied Mathematics 93 (1999) 51-66 MATHEMATICS Geometric tree graphs of points in convex position + M.C. Hernandoa,*, F. Hurtadob, A. Mb-quezC, M. Morab, M. Noyb a U. Polittbicu de Cutuhnyu, Dep. Mutemdticu Aplidu I., Diugonul 647, 08028 Burwlonu, Spuin bC’. Polithicu de Cutulunyu, Dep. Mutemciticu Aplicudu II, Puu Gu~(~uIlo 5, 08028 Burcclonu. Spuin ‘C’. de Srrillu. Dep. Mutemdticu Aplicudu I, Au. Rrinu Mrrcrdr.s sin, 41012 Sei~illu. Spuin Received I July 1997; revised 25 June 1998; accepted 22 October I998 Abstract Given a set P of points in the plane, the geometric tree graph of P is defined as the graph T(P) whose vertices are non-crossing spanning with straight edges trees of P, and where two trees TI and T2 are adjacent if T2 = TI ~ e + f for some edges e and f’. In this paper we concentrate on the geometric tree graph of a set of n points in convex position, denoted by G,,. We prove several results about G,,, among them the existence of Hamiltonian cycles and the fact that they have maximum connectivity. 0 1999 Elsevier Science B.V. All rights reserved. 1. Introduction Given a connected graph G, the tree graph T(G) is defined as the graph having as vertices the spanning trees of G, and edges joining two trees TI, T2 whenever T2 = T, - e + f for some edges e and f of G. Tree graphs were introduced by Cummings [2] in connection with the study of electrical networks, showing that tree graphs are Hamiltonian. A simpler proof of the same fact was found later by Holzmann and Harary [6], and generalized to the base graph of a matroid. Liu [X] related the connectivity of T(G) to the cyclomatic number of G. Later Liu showed that tree graphs have maximum connectivity, that is, connectivity equal to the minimum degree [9]. Additional results on tree graphs have been obtained recently [4]. Here we consider a geometric version of the problem. Given a set P of points in the plane, let 5(P) be the set of non-crossing spanning trees of P (edges are straight line segments and do not cross). We define the geometric tree graph T(P) as the graph having Y(P) as vertex set and the same adjacencies as in combinatorial tree graph, that is, two non-crossing spanning trees TI and T2 are adjacent if T2 = TI - e + ,f’. Geometric tree graphs have appeared previously in the work of Avis and Fukuda [I] ;” Research partially supported by: UPC Research Project PR-9410 and DGES-MEC-PB96-0005-C02-02. * Corresponding author. E-mail: [email protected]. 0166-218X/99/$ -see front matter 0 1999 Elsevier Science B.V. All rights reserved. PII: SO 166-2 18X( 99)00006-2 52 A4. C. Hernando et al. I Discrete Applied Murhrmutics 93 (1999) 51-66 as a tool for enumerating spanning trees. They show that T(P) is connected for any point set P in general position and has diameter bounded by 2n - 4 if n = IPl. In this paper we concentrate on the combinatorial properties of the graphs T(P) in the case where P is a point set in convex position. For any n 3 2, we denote G, the geometric tree graph of a set of n points in convex position. In this paper we obtain a number of new results about the graphs G,. In Section 2 we give definitions and preliminary results as the minimum and the maximum degree of G,,. In Sections 3 and 4 we determine the radius, and the group of automorphisms of G,. We also show that the diameter of G,, is at least 3n/2 - 5. In Section 6 we present a tree qf geometric trees, a recursive construction of the graphs G, in which a tree T in G, gives rise to ( > di2 different trees in G,+i, where d is the degree of the n-th vertex in T. This tool is then used to produce inductive proofs of two main results: G, is a Hamiltonian graph for every n 33, and G, has connectivity equal to the minimum degree 2n - 4. We remark that this kind of construction has proved useful in solving similar problems for graphs of triangulations instead of tree graphs [7]. To determine the exact value of the diameter is the main open problem left in this paper. In the case of combinatorial tree graphs, the diameter is obviously bounded by n - 1, because spanning trees satisfy the exchange property of the set of basis of a matroid. But this ceases to be true in the geometric case. 2. Definitions and preliminaries 2.1. Geometric tree graphs Let P = { 1,. . . , n} be a set of points in the plane, no three of them collinear. A non-crossing spanning tree for P is a spanning tree of P with edges given by straight line segments that do not cross. Let F(P) be the set of non-crossing spanning trees of P. The geometric tree graph T(P) of the set of P has a vertex for every element of F(P) and two trees TI, TzEF(P) are adjacent, and we write TI N T2, when there are edges e E T, \T2 and f E Tz\T, such that T2 = Tl + f - e. An example is shown in Fig. 1 2.2. The graph G, Since any two sets of points, both in convex position, are equivalent with respect to their non-crossing spanning trees, all sets of n points in convex position have the same geometric tree graph, denoted simply by G, (Fig. 2). So we are free to work with the set of P,, of vertices of a regular polygon. We assume, without loss of generality, that its vertices are labelled by integers 1 to n, sorted counterclockwise, and that 1 is the vertex with minimum x-coordinate. The arithmetic of the indices is done modulo n. M. C. Hernundo et al. I Discrete Applied Mathematics 93 (1999) 51-66 0 . 0 0 l l l Fig. 1. Two trees adjacent in .Y(P). Fig. 2. The graph G+ Let us denote by Yn the set of all non-crossing spanning trees of P,, that is, the vertex set of the graph G,. We summarize next what is known about the graphs G,. (i) G,* is connected and has diameter bounded above by 2n - 4 [ 11. (ii) The number of vertices of G, is tn = 1/(2n- 1) (:I:) [3,10], and every geometric tree graph of a set of n points has at least this number of vertices [5]. (iii) The chromatic number of G, is in @(n2) [4]. We finally remark a very useful property that will be used in the following sections. 54 M. C. Hernando et al. I Discrete Applied Mathematics 93 (1999) 51-66 Remark 2.1. Any tree T E &, n 23, has at least two edges on the boundary of P,,, that is, two edges of the type (i, i + l), and such that either the vertex i or the vertex i + 1 is a leaf of T. 2.3. Maximum and minimum degree The degrees of the vertices of G, can be quite different. There are vertices with degree O(n) and vertices with degree @(n3), as shown below. There are some trees with a specially simple structure called stars. The star Si is obtained by joining the vertex i to all the other vertices. Note that for n = 2,3 all trees are stars. In order to obtain an adjacent tree of Fa from a star Sj we can only add an edge of the boundary of P,, that is not in Si. There are n - 2 edges of this kind. If (k, k + 1) is one of these edges, when it is added we must remove either the edge (i, k) or the edge (i, k + 1) of the cycle that appears in Si U (k, k + 1). Then we conclude that the degree of a star in G, is 2(n - 2). Let de(i) denote the degree of a vertex i in a graph G and 6(G) and d(G) the minimum and the maximum degree, respectively. Proposition 2.2. 6(G,) = 2n - 4 and only the stars have this degree. Other special trees are the chains. The chain Ci is obtained by taking all the edges in the boundary of P,,, except (i, i + 1). Proposition 2.3. d(G,) = (“:I) - n + 1 and only the chains have this degree. The proof of both results is by induction on n, removing a vertex of degree one incident to a boundary edge and considering the different cases that arise. 3. Center, radius and diameter In this section we continue the study of properties of the graph G,,. We will denote by d( T, T’) the distance in G, between two trees T and T’ of Fn, that is, the minimum number of edges we have to change from one of these trees in order to obtain the other one, so that at each exchange the resulting tree is non-crossing. The eccentricity e(T) of T E YR, is defined as the maximum distance between T and any other tree in F,,. The radius of the graph G, is the minimum of the eccentricities of the vertices of G,, and the center of G, is the set of all vertices that have eccentricity equal to the radius. Remark 3.1. Let TEF~ and let di be the degree of i in T, for 1 <i<n. Then d(T,&)= n - 1 -di (see [l]). M. C. Hernando et al. I Discrete Applied Mathematics 93 (1999) 51-66 55 T T Fig. 3. <h(r) = ch(T’),dr(i) = dr,(i)Vi. Remark 3.2. Let TEF~ and let ch(T) be the number of edges of T in the boundary of P,. Then d(T,Ci)=n-ch(T) if (i,i d(T,Ci)=n - 1 -c/z(T) if The following result shows that graph. fl)~ T, (i,i + 1) @ T. the stars and the chains play a special role in the Theorem 3.3. The radius of G, is equal to n - 2, and the center contains of the n stars Sl,..., S,, and the n chains Cl,. . , C,. Proof. From Remark 3.1 it is obvious that the eccentricity of a star is equal to n ~ 2, because any tree has at least one edge in common with any star. Since all trees T E & have two edges on the boundary of P,,, the eccentricity of a chain is also n - 2. It remains to show that if a tree T is neither a star nor a chain, then e(T) an - 2. It is sufficient to show that, for any of these trees T there is another T’ that shares at most one edge with T, because then it is clear that d( T, T’) 3n - 2. One removes a vertex of degree 1 incident to a boundary edge and the existence of T’ is easily proved by induction. q Remark 3.4. From Remarks 3.1 and 3.2 the distances from a tree to the stars and the chains are easily computed. One could think that these distances determine the tree. This is not so, moreover, as shown in Fig. 3, one can find two different trees with the same degree sequences and even the same edges on the boundary. After having established the value of the radius, it is natural to ask about the diameter, that is, the maximum of the eccentricities of the vertices of G,. An obvious upper bound for the diameter is twice the radius, i.e. (2n - 2), and a trivial lower bound is n - 1. We give here a more precise lower bound. Let n be even, and let T, and T2 be the following trees (see Fig. 4): 56 M. C. Hernando et al. I Discrete Applied Mathematics 93 (1999) 51-66 T T I 2 Fig. 4. Two trees with d(T,, T2) = 3n/2 - 5. Theorem 3.5. The diameter oj’ G, is at least [3n/2J - 5. Proof. We prove here the case when n is even. The case when n is odd is handled with a slight modification of the trees T, and T2 defined above. The edge e = (2, n) E T2 in an edge of T2 that has the minimum number of crossings with the edges of T,, and e intersects n/2 - 1 edges of TI. We need at least n/2 - 1 changes before we can add the first edge of T,. In the best case, we need a change for introducing each of the remaining edges of T, that do not appear in TI. As TI and T, have in common two edges, we obtain d(T1,Tz)3 ; - ( > 1 + (n - 4) = ; - 5. Finally, it is easy to find a path between Tl and T2 that has exactly this length. 0 Taking into account this result, in order to maximize the eccentricity, we observe that after Remarks 3.1 and 3.2 we can conclude the following. If T E Fn and ch( T) an/2 or there is some vertex i such that dT(i) > n/2, then e(T) d 3n/2 - 2. Then, it is natural to consider those trees that have few edges in the boundary of P, and vertices with low degree. But we have obtained that if T E F” is such that ch(T)=2, then e(T) <3n/2-2. 4. Group of automorphisms Let us denote by T(G,) the automorphism group of G,,. It is clear that any symmetry of the regular n-polygon will induce a corresponding automorphism on G,,. No more automorphisms are possible, as proved next. Theorem 4.1. The automorphism group T(G,,) is isomorphic to the dihedral group D, of the symmetries of a regular polygon with II sides. Proof. Let us consider the set of starts and chains 57 = {Si, . ..) &Cl )...) Cn}. M. C. Hernando et al. I Discrete Applied Mathematics 93 (I 999) 51-66 57 Moreover, it is straightforward to see that d(S,, S, ) = n - 2, A(C;, Cj) = 1, d(C,,S;)=n-2 ifj=iorj=i+l, d( C,, S, ) = n - 3 otherwise. Now let y be in I’(G,). Since the S, are the vertices of minimum degree and the C, are those of maximum degree, we see that 7({&,..., &>)= {&,...,&), ll<{cl,...,cn})={cl,...~cn>. If y(Sr)=Sj, as d(S,,Cl)=d(S,,~(C,)), then either y(Cr)=C; or l/(Ct)=C,_t. In the first case it follows that y(C2) = C,+t , and in the second case that >(Cz) = C,_z. Proceeding in this way, we see that y is either a rotation or a reflection of the index set (1,. . . , n}. This shows that the restriction of T(G,) to the set Z is equivalent to the dihedral group D,. That action on the set Z is crucial, as we conclude next by proving that 71,~ = ~1~ implies 7 = p. Equivalently, we are going to show that if Y,,J = 1, y then 7 = 1. Before proving this, assuming ~13 = 112, we make two remarks. (i) Let T be any tree and di=dr(i) the degree of T on the vertex i. From Remark 3.1 we know that d( T,S,) = n - 1 - di. But, by hypothesis, ;’ is trivial on the stars, and an automorphism preserves distances, hence d(]‘( T), Sj) = d(y( T), r(lSi)) = n( r, Si) = ?I - 1 - d, and the vertex i has the same degree in T and y(T) for any i, 1 <i<n. (ii) On the other hand, if c/z(T) is the number of edges that T has in the boundary, then d(:j(T),C,)=d(y(T),y(C,))=d(T,C;)=n-A(T) if (i,i+l)ET, d(;i(T),Ci)=d(y(T),y(C*))=d(T,C,)=n- 1 -CA(T) if (i,i+ 1) @r, hence T and y(T) have the same edges in the boundary. We prove now that if 7’1~ = 1 then ‘/ = 1, by induction on the number of vertices. Let U be any tree of Yn, we want to show that y(U) = U. Let i be a vertex such that du(i) = 1 and (i, i + 1) E U and let r( U ) be the following set of trees in ,&, F(U)={T l .YJdr(i)= l,(i,i+ 1)~ r}. We remark that after (i) and (ii) we can ensure that 7(9-(U)) C Y(U) and since ;I is bijective, we have y(Y(U)) = F(U). In particular, it makes sense to consider the automorphism ;‘l_r-(u), the restriction of 7 to the set .Y( U ). Besides, identifying P,,- 1 with P, \ {i}, the subgraph induced on Y(U) is isomorphic to G,_l. It is straightforward to verify that ;‘I.F(~~) restricted to the set of stars and chains of G,_, is the identity and applying induction we have that y~_~(u) is the identity on G,,_t . We conclude that y(U) = U for all U E ,Tn. So, 7 = 1. 0 58 M. C. Hernando et al. I Discrete Applied Mathematics 93 (1999) 51-66 5. Tree of geometric trees In this section we describe the main tool for proving the results that appear in the next two sections, on the Hamiltonicity and the connectivity of the graph G,. This tool is a recursive construction of the graphs G, in which a tree T of G, gives rise to ( > d12 different trees of Gn+i . In this way we obtain an infinite tree, whose vertices are the trees in Yn, for all n. This kind of construction has proved useful in solving similar problems for graphs of triangulations [7]. In this infinite tree, every T E & has one father, belonging to rn-lr and some sons, belonging to Yn+l. If T E Fn is such that il < i2 < . . . < id are the vertices adjacent to n in T, we construct its sons Si,j(T) as the trees of &+i defined as follows. We distinguish three kinds of sons: Type 0: We add the edge (n, n + 1) to T and distribute between n and n + 1 the edges (ik,n) of T: so,o(T) = T U {(n, n + 1)) and for k, 1 dkdd, S~,k(T)={(a,b)lu,~#n, (~,~)~T}U{(~+l,i,)(ldp~k}U U{(n,i,> I kfpdd} U {(n,n + 1)). Type 1: We split the edge (ik,n) into the two edges (ik,n) and (&,n + 1). for ldkbd. Type j,j 2 2: For every subset S of cardinal&y j of { il,. . . , id}, s={ ik, &+I,. . . , ik+j_ I}, we build the chain n + l,ik,ik+l,...,ik+j-l,n: ~j,k(T)={(U,b)(U,b#~,(U,b)ET)U((~+1,i,)Il~pbk} U{(n,i,)Ikfpdd -j+2} U{(ik,ik+l h(ik+l,ik+2),. . .,(ik+j--2,ik+j-I)). In Fig. 5 we show all the sons of the star S, E .Yb. The sons of type 0 are at the first floor, those of type 1 at the second one, and so on. The number of sons of a tree T E 9” depends on the degree of n in T. More exactly, if this degree is d, then the number of sons of T is (d+l)+d+(d-l)+...+l=(d+2)2(d+1)= d;2 . ( > We observe that, given a tree T E Fn+l, T has a unique father. This father can be obtained by identifying IZ and n + 1 and connecting n to all verties adjacent to n or M. C. Hernundo et al. I Discrete Applied Muthemutics Y3 (IWY) 51-66 59 Fig. 5. Construction of the sons S,,k(&) of the star S4 E 3~. n + 1 in T, and to all the vertices belonging to the path between n and n + 1 in T. We see that this procedure generates all the trees of ,Yn+r from the trees of .&. We observe that any T has always the sons Se,o(T) and &d(T). These sons are a copy of T with a pending edge (n, II + 1 ), and will play an important role later. We denote them by F(T) and L(T), respectively. F and L stand for jfirst and lust, a name that will become clear later. If T E & is a son of T, E Yn_l, we say that T, is a father of T and we write T, = f(T). If TI, Tz have the same father, we say that T, and T2 are brothers. The father f(T) of T is easily obtained by reversing the process. The father is unique, hence we have an (infinite) tree as follows. Taking the unique vertex of G2 as the root of this tree, at level n - 1 we have all the trees of rFn that is, the vertices of G,. In Fig. 6 we can see the first three levels of the tree. The adjacencies in the graphs G, are lifted up and down through the tree just constructed in a way we describe in the next two lemmas, which are immediate. Lemma 5.1. Let TI, T2 E &. The folloti+ny properties hold (a) TI, T2 are adjacent tf and only if F( T1 ), F(T2) are adjacent and L( T, ), L( T,) ure also adjacent. (b) If T1, Tz are adjacent and (i, n) E T, f’ T2, und il < . . . < i = i, < . < id are adjacent to n in T1, and jl < < j, = i < . < j,t are adjacent to n in Tz, then Sj,i(TI),Sj.;(T2) are adjacent for j = 1,2. (c) [f Tl, T2 are adjacent and have in common all the edges adjacent to n, then S,.k( TI ) und Sj,k( T2) are adjacent for all j, k. Lemma 5.2. The sons of T induce a subgraph *Yr in G,,+l that has the following properties: 66 M. C. Hernando et al. IDiscrete Applied Mathematics 93 (1999) 51-66 Finally, if s = 2, by 1, we have at least 2n - 2 - (4 + 4) = 2n - 10 trees in different families. Consider now the trees T + (1, n) - ( jt , n), T + (1, n) - e, where e is in Tj,,b and in the cycle formed when adding edge (1,n) to T, and T+(n-2,n- I)-(jl,,- l), T + (n - 2, n - 1) - f, where f is in Tj,,f and in the cycle formed when adding edge (1,n) to T. In this way, we obtain four trees that are not in Yf(r), and no more than two are in the same family. This implies that we have to remove, besides the two vertices of L+(r), 2n - 10 + 4 = 2n - 6 vertices to disconnect T from F and L, that is 2n - 6 + 2 = 2n - 4 vertices. This finishes the proof of the claim and the proof of the theorem. 0 7. Conclusions and open problems We have obtained many basic properties of the graphs G,. We consider that to determine exactly the diameter is the main open problem left in this paper. An efficient algorithm for finding shortest paths in G, would also be interesting. On the other hand, when the set P of points is not in convex position, it would be interesting to relate the position of the points to the properties of T(P), as well as to try to characterize the graphs which are geometric tree graphs for some P. Acknowledgements We are grateful to one of the referees for a very careful revision of the paper and for many valuable suggestions. References [ 1] D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Appl. Math. 6 (1996) 2146. [2] R.L. Cummings, Hamilton circuits in tree graphs, IEEE Trans. Circuit Theory 13 (1966) 82-90. [3] S. Dulucq, J.G. Penaud, Cordes, arbres et permutations, Discrete Math. 117 (1993) 89-105. [4] V. Estivill-Castro, M. Noy, J. Urrutia, On the chromatic number of tree graphs, in preparation. [5] A. Garcia, M. Noy, J. Tejel, Lower bounds on the number of crossing free subgraphs of K,, Proceedings of the 7th Canadian Conf. on Computational Geometry, 1995, pp. 97-102 (also to appear in Comput. Geometry: Theory Appl.). [6] C.A. Holzmann, F. Harary, On the tree graph of a matroid, SIAM J. Appl. Math. 22 (1972) 187-193. [7] F. Hurtado, M. Noy, The graph of triangulations of a convex polygon, Technical Report MA2-IR-94-13, Universitat Politecnica de Catalunya (1995) ( an abstract has appeared in Proceedings of the 12th ACM Symposium on Computational Geometry, 1996, pp. C7-C8), to appear in Comp. Geom.: Theory Appl. [8] G. Liu, On connectivities of tree graphs, J. Graph Theory 12 (1988) 453459. [9] G. Liu, Paths between vertices in a graph, System Sci. Math. Sci. 5 (1992) 108-l 10. [lo] M. Noy, Enumeration of non-crossing trees on acircle, Discrete Math. 180 (1998) 301-313.