Diagonal flips in outer-torus triangulations

Diagonal ips in outer-torus triangulations Carmen Cortesa, Atsuhiro Nakamotob;∗ aDepartamento of Matematica Aplicada I, Univ de Sevilla, Escuela Universitaria Arquitectura Tecnica, Avda Reina Mercedes S/N, 41012 Sevilla, Spain bDepartment of Mathematics, Osaka Kyoiku University, 4-698-1 Asahigaoka, Kashiwara, Osaka 582-8582, Japan Received 12 October 1997; revised 15 April 1999 Abstract An outer-torus triangulation G with n vertices is a xed embedding of a simple graph on the torus such that there is one face bounded by a cycle of length n and other faces are all triangular. We show that any two outer-torus triangulations with the same number of vertices can be transformed into each other by a sequence of diagonal ips, through outer-torus triangulations, up to homeomorphism. 1. Introduction Throughout this paper, we deal with only simple graphs (i.e., graphs without loops and multiple edges) which have already been 2-cell embedded in closed surfaces. For a graph Gon a closed surface, we denote the vertex-set, the edge-set and the face-set of Gby V(G);E(G) and F(G), respectively. Atriangulation Gof a closed surface F2is a simple graph on F2such that each face is bounded by a 3-cycle and any two faces share at most one edge. (A k-cycle is a cycle of length k.) The second condition is needed only to exclude K3from the spherical triangulations. Let Gbe a triangulation of a closed surface F2. Suppose that ac ∈E(G) is shared by two faces abc and acd.Adiagonal ip of the edge ac is to replace ac by bd,as shown in Fig. 1. If the resulting graph by a diagonal ip is not simple, then we do not apply it. For the sphere, the torus, the projective plane and the Klein bottle, it has been shown that any two triangulations with the same number of vertices can be transformed into each other by a sequence of diagonal ips, up to homeomorphism [2,11,12]. Negami has ∗ Corresponding author. E-mail addresses: [email protected] (C. Cortes), [email protected] (A. Nakamoto) 72 C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 Fig. 1. A diagonal ip. shown in [6] that any two triangulations of the same closed surface can be transformed into each other by diagonal ips, up to homeomorphism, if they have the same and suciently large number of vertices. This theorem is a starting point of many researches for diagonal ips in triangulations done in [1,4,5,7–10]. In this paper, we consider diagonal ips in other kind of triangulations. An outer triangulation Gof a closed surface F2is a simple graph on F2such that there exists a specic face Fof G, called the outer face, on whose boundary each vertex of G appears exactly once, and other faces are all triangular. (The boundary cycle of Fis called the boundary of G.) Since a diagonal ip is applied in a quadrilateral region formed by two adjacent triangular faces, a diagonal ip in an outer triangulation G must be applied for edges not on the boundary of G. It is easy to show that any two outer triangulations of the sphere (i.e., maximal outer-plane graphs) with the same number of vertices can be transformed into each other by diagonal ips. Moreover, it has been shown in [3] that the same fact holds for outer triangulations of projective plane. Mimicking Negami’s argument in [6], one will be able to show that two triangulations on a punctured surface with the boundary cycle of xed length can be transformed into each other by a sequence of diagonal ips if they have the same and suciently large number of vertices. However, they have to include many vertices not lying on the boundaries. It seems to be dicult to establish a similar theorem for outer triangulations of general surfaces. In this paper, we consider the toroidal case and show the following theorems. We call an outer triangulation of the torus simply an outer-torus triangulation. Theorem 1. Any two outer-torus triangulations with the same number of vertices can be transformed into each other by a sequence of diagonal ips;up to homeomorphism. To show Theorem 1, we prove the following theorem which is more elaborated with respect to the minimum degree. In general, the minimum degree of outer-torus triangulations is at least 2. However, if given two outer-torus triangulations have minimum C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 73 Fig. 2. The unique outer-torus triangular embedding of K6. degree at least 3, then we can preserve the minimum degree at least 3 in the sequence of diagonal ips connecting them, as in the following theorem. Theorem 2. Any two outer-torus triangulations with minimum degree at least 3can be transformed into each other by a sequence of diagonal ips;up to homeomorphism; preserving the minimum degree at least 3;if they have the same number of vertices. We also consider the vertex-labeled version of Theorem 1. The vertex labeling of a graph Twith nvertices is a bijection :V(T)→{1;:::;n}. Let Gand G0 0be vertex-labeled outer-torus triangulations with nvertices whose boundaries are labeled by 1234 ···nand 1324 ···n, respectively. Since no diagonal ip can move edges on the boundary of Gand G0 0;G and G0 0cannot be transformed into each other by a sequence of diagonal ips so that their vertex labelings completely coincide. Thus, a necessary condition for two vertex-labeled outer-torus triangulations to be transformed into each other by diagonal ips is that the vertex labelings of their boundaries are equivalent, up to cyclic permutation. Theorem 3. Any two vertex-labeled outer-torus triangulations with the same number of vertices can be transformed into each other by a sequence of diagonal ips;up to homeomorphism;if and only if the vertex labelings of their boundaries are equivalent; up to cyclic permutation. By the same extension, Theorem 3 with the minimum degree condition also holds. It has been shown that the triangulation of the torus with the fewest number of vertices is the unique triangular embedding of the complete graph K7with 7 vertices. Removing one vertex from this yields K6in which there is one hexagonal face on whose boundary all the vertices appear, and other faces are all triangular. See Fig. 2, where the rectangle shows the torus by identifying the opposite sides in parallel and the dashed segments never express edges of the graph. Throughout this paper, we use such a presentation for the torus. Clearly, this is the smallest outer-torus triangulation. 74 C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 In order to show our main theorem, we also show that any outer-torus triangulation can be transformed into the outer-torus embedding of K6by contractions of edges on the boundary and diagonal ips of edges not on the boundary. 2. Pseudo-minimal outer-torus triangulations Let Gbe an outer-torus triangulation and let Fbe the outer face of Gand Cthe boundary cycle of Fthroughout this section. Let e=xy ∈E(C) such that xyz(6=C) bounds a triangular face of G. The edge-contraction of e(or simply contracting e)is to contract eand replace the multiple edges {xz; yz}by a single edge. Note that an edge-contraction is dened only for edges on the boundary. An edge e∈E(C) is said to be contractible if the graph obtained from Gby contracting eis also an outer-torus triangulation, that is, one without loops and multiple edges. An outer-torus triangulation Gis said to be pseudo-minimal if (i) Ghas no contractible edge, and (ii) no sequence of diagonal ips can transform Ginto one with contractible edges. For example, K6is a pseudo-minimal outer-torus triangulation since it has no contractible edge and every diagonal ip transforms this into a non-simple graph. (Throughout this paper, we denote the unique outer-torus triangular embedding of K6 by simply K6.) This section is devoted to showing the following theorem. Theorem 4. Every outer-torus triangulation can be transformed into K6by a sequence of diagonal ips and edge-contractions;up to homeomorphism. Clearly, it suces to show that the only pseudo-minimal outer-torus triangulation is K6. So we show that any other outer-torus triangulation is not pseudo-minimal. Lemma 5. If |V(G)|¿7;then Ghas a vertex of degree at most 4. Proof. By Euler’s formula, we have |V(G)|−|E(G)|+|F(G)|=0: Since Fis bounded by a cycle of length |V(G)|, and other faces by 3-cycles, we have |V(G)|+3(|F(G)|−1)=2|E(G)|: Eliminating |F(G)|by the two equations, we obtain 2|E(G)|=4|V(G)|+6: Thus, the average degree  d(G)is  d(G)=2|E(G)| |V(G)|=4+ 6 |V(G)|: C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 75 Since |V(G)|¿7, we have  d(G)¡5. Therefore, Ghas a vertex of degree at most 4. Lemma 6. If Gis pseudo-minimal;then Ghas no vertex of degree 2: Proof. Suppose that Ghas a vertex vof degree 2. Let x; y be the neighbors of v and the edge xy is supposed to be shared by two triangular faces vxy and uxy. After replacing the edge xy with uv by a diagonal ip, we can contract vx in the resulting graph G0since xy 6∈ E(G0), contrary to the pseudo-minimality of G. Let Dbe a closed curve (or a loop) on a closed surface F2, that is, a continuous function D:S1→F2or its image, where S1is the one-dimensional unit sphere. We say that Dis trivial if D(S1) bounds a 2-cell on F2, while Dis essential otherwise. Two simple closed curves (or loops) D1and D2on F2are said to be homotopic if there is a continuous function :[0;1]×S1→F2such that (0;x)=D1(x) and (1;x)=D2(x) for each x∈S1. Let e=uv ∈E(G)−E(C). We say that eis trivial if Gcan be separated by einto an outer-plane triangulation G1and an outer-torus triangulation G2such that G1∩G2=e. Otherwise, eis essential. Shrinking the outer face Fof Ginto one vertex on the torus, we obtain the graph ˜ Gon the torus with exactly one vertex and many loops. A trivial edge of Gwill be deformed into a trivial loop in ˜ G, while an essential edge will be an essential loop in ˜ G. Two edges e1;e 2∈E(G)−E(C) are said to be homotopic if in the graph ˜ G; e1and e2are deformed into two loops homotopic to each other. Lemma 7. Each edge e∈E(G)−E(C)is essential if and only if Ghas no vertex of degree 2: Proof. We rst show the necessity. If Ghas a vertex vof degree 2 with neighbors u1 and u2, then u1and u2must be adjacent and the cycle vu1u2bounds a face of G. The edge u1u2is obviously trivial. Thus, the necessity holds. Secondly we show the suciency. Suppose that Ghas a trivial edge e=uv. Then eseparates Ginto an outer-plane triangulation G1and an outer-torus triangulation G2 such that G1∩G2=e. It is well-known that every maximal outer-planar graph, except K3, has two nonadjacent vertices of degree 2. Thus, G1has a vertex w∈V(G1)−{u; v} of degree 2 and the vertex whas degree 2 in G, too. The following lemma is straightforward by Lemmas 6 and 7. Lemma 8. If Gis pseudo-minimal;then each edge e∈E(G)−E(C)is essential. Lemma 9. If Gis pseudo-minimal;then Ghas no vertex of degree 3: Proof. Suppose that Ghas a vertex vof degree 3. Let x; y; z be the neighbors of v, where vx; vz ∈E(C) and vy 6∈ E(C). Consider a simple closed curve Lalong vy and through the center of F. By Lemma 8, Lis essential. 76 C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 Fig. 3. Gcut along Land L0. Since the edge vx is not contractible, Ghas an edge xz. We have xz 6∈ E(C) and xz is essential, by Lemma 8. (For if xz ∈E(C), then |V(G)|= 3, a contradiction.) Consider a simple closed curve L0along xz and through the center F. Since Land L0cross at one point in the center of F, cutting the torus along Land L0yields a rectangle shown in Fig. 3. Next we see two triangular faces xza and xzb containing the edge xz. In Fig. 3, there are two thick lines between yand x, and between y and z, which express the paths yp1···pnxand yq1···qmz, respectively. Observe that each path has length at least 2. Otherwise, we can nd multiple edges xy or yz. Let P={p1;:::;p n}6=∅and Q={q1;:::;q m}6=∅. Notice that there is an edge between aand b. (Otherwise, after replacing xz with ab by a diagonal ip, we can contract the edge vx, contrary to the pseudo-minimality of G.) Since Gis simple and each vertex appears on the boundary Cof G, each of a and bmust coincide with a vertex in P∪Q. Up to symmetry, it suces to consider the following two cases. Case (1): a; b ∈P. First suppose that a=piwith i¿3. Then, in the 2-cell region bounded by xyp1:::p i, we have pspt6∈ E(G)−E(C) for any s; t with 16s¡t6i, by Lemma 8, and hence each of p2;:::;p i−1is adjacent with xand has degree 3. Thus, the edge p1p2is contractible since yand p3are distinct vertices. Thus, either a=p1or a=p2.By Lemma 8, we have b=pn, and moreover a=pn−1since ab ∈E(C). The leftand right-hand side in Fig. 4 show the cases when a=p2and a=p1, respectively. In the left-hand gure, since p1p2is not contractible, p2y∈E(G). Replace p2x with p1z, and xz with p1p3by diagonal ips in this order. Then, the edge vx is contractible, a contradiction. In the right-hand gure, let p1zc be the triangular face sharing p1zother than p1zx. Then we must have c∈Qand suppose that c=qi. Since we cannot join xand qito make G, a diagonal ip can replace p1zwith xqi.Inthe resulting graph ˜ G,ifp2and qiare not adjacent, then after replacing xz with p2qi, the edge vx is contractible, a contradiction. On the other hand, the case when p2and qi are adjacent in ˜ Gcan be regarded as the case when a∈Qand b∈P, which is a symmetric case of Case (2). C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 77 Fig. 4. Case when a; b ∈P. Fig. 5. Case when a∈Pand b∈Q. Case (2): a∈Pand b∈Q. By the same argument as in Case (1), either a=p1or a=p2, and b=qmand ab ∈E(G)−E(C). Here we have to notice that a=pn−1. (Clearly, a6=pnsince G has no multiple edges. If a=pifor some i6n−2, then the edge pn−1pnis contractible, as in Case (1).) Moreover, by Lemma 6, pnis adjacent with qm. See Fig. 5. Consider whether or not the edge ab(=pn−1qm) can be ipped. The diagonal ip of pn−1qmis forbidden only if the diagonal ip of pn−1qmmakes multiple edges between pnand xsince the neighbors of pnis {pn−1;q m;x}. Though we don’t know the complete structure of Gyet, the boundary zyq1···qmpn−1of the remaining region does not contain x, and hence such bad case does not happen. Thus, we can apply the diagonal ip of pn−1qm. After the diagonal ip, the edge xz can be replaced with pn−1qm, and in the resulting graph, the edge vx is contractible, a contradiction. Lemma 10. If Gis pseudo-minimal;then Ghas no vertex of degree 4: Proof. Suppose that Ghas a vertex vof degree 4. Let x; y; z; w be the neighbors of vin Gin the cyclic order, where vx; vw ∈E(C). If either xz 6∈ E(G)oryw 6∈ E(G), 78 C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 Fig. 6. Case when yz ∈E(C). then we can apply a diagonal ip of vy or vz, respectively, and hence we can reduce the degree of vand Lemma 9 can be applied. So, we have xz; yw ∈E(G). We consider the following two cases depending on whether or not the edge yz is contained in C. In order to cut open the torus into a rectangle, we have to nd a pair of closed curves on the torus which cross each other at one point. Case (1): yz ∈E(C) Consider two closed curves Land L0on the torus (where Gembeds) through the center of the outer face Fof Gsuch that Land L0are along the edges xz and yw, respectively. Since yz ∈E(C) in this case, the union of the four faces F; vxy; vyz and vzw forms an annulus on the torus, not a Mobius band, and hence the ve vertices x; v; w; z; y appear on Cin this cyclic order. Thus, we have xz; yw 6∈ E(C), and Land L0cross exactly once in the center of F. Cut open the torus along Land L0. See the left-hand in Fig. 6. In the left-hand gure, two thick lines between zand w, and between yand xexpress paths of length at least 2, denoted by zp1···pnwand yq1···qmx, respectively. Let P={p1;:::;p n}6=∅and Q={q1;:::;q m}6=∅. Let aand bbe the two vertices, other than yand w,oftwo triangular faces sharing the edge yw, as shown on the left-hand in Fig. 6. By Lemma 9, we may suppose that each vertex has degree at least 4. If a=x, then each pimust have degree 3 by Lemma 8, a contradiction. Thus, we must have a=pnby Lemma 8 again. By the same argument, we can conclude that b=q1, as shown on the right-hand side in Fig. 6. Since pnq16∈ E(G), we can ip vz after the diagonal ip of wy.We have decreased the degree of vand we can apply Lemma 9. Case (2): yz 6∈ E(C). Consider two closed curves Dand D0on the torus (where Gembeds) through the center of Fsuch that Dand D0are along xy and wz, respectively. Since degG(x)¿2; degG(w)¿2, we have xy; wz 6∈ E(C). First suppose that two edges xy and wz are homotopic on the torus. Then the edge yz is trivial since yz 6∈ E(C), contrary to Lemma 8. Thus, xy and wz are non-homotopic and hence Dand D0are pairwise non-homotopic essential closed curves crossing only at the center of F. C. Cort es, A. Nakamoto / Discrete Mathematics 216 (2000) 71–83 79 Fig. 7. Case when yz ∈E(G)−E(C). Cutting open the torus along Dand D0, we obtain the left-hand side in Fig. 7. The three thick lines between yand w, between zand x, and between yand zexpress paths yp1:::;p nw,zq1···qmxand yr1···rlz, respectively. Let P={p1;:::;p n},Q= {q1;:::;q m}and R={r1;:::;r l}. Notice that R6=∅. (For otherwise, yz would be multiple edges.) Remember yw; zx ∈E(G) since the degree of vcannot be decreased. If P6=∅, then yand wmust be joined. However, if they are joined, then each rihas degree 3 by Lemma 8. Thus, P=∅. By the symmetric argument, we have Q=∅. Consider the triangular faces ayw and bzx incident with yw and zx, respectively. Each of aand bcoincide with one of r1;:::;r l.Ifa=rifor some i6l−1, then all of ri+1;:::;r lhave degree 3 by Lemma 8, a contradiction. Thus, we have a=rland similarly b=r1, as shown on the right-hand side in Fig. 7. Here, since vand rlcannot be joined, the edge wz can be replaced with vrlby a diagonal ip. In the resulting graph, whas degree 3 and apply Lemma 9. Now we can show Theorem 4. Proof of Theorem 4. Suppose that there is a pseudo-minimal outer-torus triangulation Gother than K6with at least 7 vertices. Then, by Lemmas 5 and 6, the minimum degree of Gmust be either 3 or 4. However, it is impossible, by Lemmas 9 and 10. Therefore, the torus admits a unique pseudo-minimal outer-torus triangulation K6, up to homeomorphism. By the denition of pseudo-minimality, every outer-torus triangulation except K6has a contractible edge after several diagonal ips. Since each edge-contraction reduces the number of vertices by 1, it will reach 6, and hence the theorem follows. Theorem 4 can be strengthened with respect to the minimum degree condition. Theorem 11. Every outer-torus triangulation with minimum degree at least 3can be transformed into K6by a sequence of edge-contractions and diagonal ips;preserving the minimum degree at least 3;up to homeomorphism.