Diagonal flips in outer-triangulations on closed surfaces

Discrete Mathematics 254 (2002) 63–74 www.elsevier.com/locate/disc Diagonal ips in outer-triangulations on closed surfaces Carmen Cort%esa;1Clara Grimaa;1Alberto Marqueza;1 Atsuhiro Nakamotob;∗ aDepartamento of Matem atica Aplicada I, Univ. de Sevilla, Sevilla, Spain bDepartment of Mathematics, Osaka Kyoiku University, 4-698-1 Asahigaoka, Kashiwara, Osaka 582-8582, Japan Received 8 February 2000; received in revised form 10 October 2000; accepted 7 May 2001 Abstract We show that any two outer-triangulations on the same closed surface can be transformed into each other by a sequence of diagonal ips, up to isotopy, if they have a su6ciently large and equal number of vertices. c 2002 Elsevier Science B.V. All rights reserved. Keywords: Triangulation; Outer-triangulation; Diagonal ip 1. Introduction In this paper, we always suppose that a graph Gis embedded in a closed surface, and the vertex set, edge set and face set of Gare denoted by V(G);E(G) and F(G), respectively. In addition, all embeddings considered here will be 2-cell embeddings. A k-cycle means a cycle of length k. A closed curve ‘on a closed surface F2is said to be 1-sided if the tubular neighborhood of ‘is homeomorphic to a M>obius band, and 2-sided otherwise. Atriangulation on a closed surface F2is a simple graph on F2such that each face is bounded by a 3-cycle, and any two faces share at the most one edge. A diagonal +ip in a triangulation Gis to replace a diagonal ac with bd in the quadrilateral abcd ∗Corresponding author. E-mail addresses: [email protected] (C. Cort%es), [email protected] (C. Grima), [email protected] (A. Marquez), [email protected] (A. Nakamoto) 1Partially supported by Proyecto DGICYT PB96-1374 and Proyecto PAI FQM-0164. 0012-365X/02/$ - see front matter c 2002 Elsevier Science B.V. All rights reserved. PII: S 0012-365X(01)00353-3 64 C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 Fig. 1. A diagonal ip. formed by two faces abc and acd sharing the edge ac (see Fig. 1). As we want to keep the graph simple whenever we carry out diagonal ips, we do not allow this operation if Galready has the edge bd (since, in this case, the diagonal ip would create multiple edges between band d). Let Gand Gbe two triangulations on the same closed surface. We say that Gand Gare equivalent to each other if there exists a sequence of triangulations H0;:::;H k such that (i) G=H0and G=Hk, (ii) Hi+1 is obtained from Hiby one diagonal ip, for i=0;:::;k−1. There are many papers concerning diagonal ips in triangulations. It has been shown that for the sphere [24], the projective plane [21], the torus [7] and the Klein bottle [21], any two triangulations with the same number of vertices are equivalent to each other, up to homeomorphism. Negami has generalized these theorems, as follows. Theorem 1 (Negami [16]). For any closed surface F2,there exists a natural number M(F2)such that any two triangulations Gand Gon F2with |V(G)|=|V(G)|¿ M(F2)are equivalent to each other,up to homeomorphism. This theorem has been extended for triangulations with speciNed properties [4]. Moreover, a series of theorems have been improved to hold under the condition “up to isotopy” [14]. Note that for the sphere and the projective plane, up to homeomorphism” and “up to isotopy” are equivalent. Recently, Negami [18] has given an upper bound for the minimum value M(F2) by a linear function with respect to the Euler characteristic of F2. In fact, he has shown that the linear function gives that for the corresponding value M(F2) for the isotopy version. Moreover, many other researches have been derived from Theorem 1 [10,15,17,19,20]. A very important case with many practical applications is that of triangulations of polygons in the plane (or the sphere). These triangulations agree with maximal C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 65 outerplanar graphs. Thus, we shall generalize this concept to other surfaces. A triangulation on a closed surface F2with boundary cycle C(or simply boundary)isan embedding of a simple graph on F2containing Csuch that (i) there is a speciNc face bounded by C, called the outer face, and (ii) all other faces are bounded by 3-cycles. We say that the vertices and the edges of a triangulation are outer if they lie on C, and inner otherwise. An outer-triangulation Gis a triangulation with boundary which has no inner vertices. As well as ordinary triangulations, we can deNne diagonal ips for outertriangulations. However, as any ippable edge must be shared by two triangular faces, we cannot apply diagonal ips for outer edges. Mimicking Negami’s argument in [18], one will be able to show that for any two triangulations on a closed surface with the boundary of the same length can be transformed into each other by a sequence of diagonal ips if they have the same and su6ciently large number of inner vertices. However, if we restrict the number of inner vertices, the problem seems to be far more di6cult. In this paper, we focus on outer-triangulations on surfaces. It is easy to show that any two outer-triangulations on the sphere with the same number of vertices are equivalent to each other, up to isotopy. Moreover, the same fact has been shown for the projective plane [8], the torus [5] and Klein bottle [6]. (The cases for the torus and the Klein bottle have been solved, under the condition up to homeomorphism”.) In any case, the arguments used in those papers strongly depend on the topology of these individual surfaces and they cannot be applied, in general, for other surfaces. In this paper, we will show the isotopy version of a general result, as follows. Theorem 2. For any closed surface F2,there exists a natural number N(F2)such that any two outer-triangulations Gand Gon F2with |V(G)|=|V(G)|¿N(F2)are equivalent to each other,up to isotopy. 2. Diagonal ips in outer-pseudo-triangulations Although we have to keep any triangulation simple whenever we carry out a diagonal ip, in order to prove our main result, we will neglect the simpleness of outertriangulations meanwhile, as follows. An outer-pseudo-triangulation on a closed surface F2is a pseudograph (loops and multiple edges are allowed) on F2such that there exists a speciNc face, called the outer face, bounded by the cycle in which all the vertices appear, and other faces are bounded by closed walks of length 3. A diagonal ip of an inner edge of an outerpseudo-triangulation is also deNned in the same way as previously, but the diagonal ips need not preserve the simpleness of graphs. The following theorem can be proved in the same way as in [18]. An inner edge ein an outer-pseudo-triangulation is called self-incident if there is a triangular face f such that eappears twice on the boundary walk of f. 66 C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 Fig. 2. Self-incident edge e. Lemma 3. Let Pbe an outer-pseudo-triangulation on a closed surface F2and let ebe a self-incident edge of P.Then,eisa1-sided loop whose two ends of eare consecutive in the rotation around the same vertex. Fig. 2 illustrates a self-incident edge eexplained in the above lemma, where ⊗ expresses a crosscap. Proof. Suppose that eappears twice on the boundary 3-cycle v1e1v2e2v3e3of a face f, where vi∈V(P) and ei∈E(P) for i=1;2;3. We may suppose e1=e2=e.Ifv1=v2, then v2has degree 1. The vertex v2of degree 1 cannot appear on the boundary of P, a contradiction. Thus, we have v1=v2and hence eis a loop incident to v1=v2. Since e1=e2, the right-hand neighborhood along eand its left-hand neighborhood are traced consecutively along the boundary walk of f. Therefore, eis 1-sided and the two ends are consecutive in the rotation around v2. Theorem 4. Let Pand Pbe two outer-pseudo-triangulations on a closed surface F2 with the same number of vertices.Then,they can be transformed into each other,up to isotopy,by a sequence of diagonal +ips.Furthermore,this sequence of diagonal +ips does not switch any self-incident edge. Note that by Lemma 3, if an outer-pseudo-triangulation Phas a self-incident edge e, then the graph obtained from Pby ipping eis obviously isomorphic to Pitself. Thus, the last sentence of the following theorem is trivial. The original theorem concerning psuedo-triangulations Tand T(i.e., pseudographs with each face triangular) has been proved, as follows. First, draw Tand Ton F2 simultaneously so that V(T) and V(T) completely coincide. (Thus, each intersecting point of Tand Tis either a vertex of them or a crossing of an edge of Tand an edge of Tat their middle points.) The author of [18] proceeded to Nx Ton F2and apply diagonal ips for Tto eliminate the crossings of edges. In this case, each edge eof Tpasses through the interior of several triangular faces of T, or coincides with some edge eof T. C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 67 Fig. 3. Contraction of an edge. In case of outer-pseudo-triangulations Pand P,NxPand Pon F2so that their vertices coincide along their boundaries. Then, we get the same situation that every edge eof Ppasses through the interior of several triangular faces of P, or coincides some edge eof P. Moreover, every diagonal ip in Ppreserves this condition. Thus, the same argument follows (see [18] for the details). 3. Irreducible outer-triangulations Consider an ordinary triangulation Gon a closed surface F2. Let abc and acd be two faces sharing an edge e=ac in G. The contraction of e(or contracting e)is to identify the end-vertices aand cof eand replace the multiple edges {ab; cb}and {ad; cd}by two single edges, respectively. We say that eis contractible if the graph obtained from Gby contracting eis simple. We also say that a triangulation Gis contractible to a triangulation Tif Gcan be transformed into Tby a sequence of edge contractions. A triangulation with no contractible edge is said to be irreducible. For the sphere, the projective plane, the torus and the Klein bottle, the complete lists of irreducible triangulations have been determined in [23,1,11,12], respectively. It is well-known that any closed surface admits only Nnitely many irreducible triangulations, up to homeomorphism. This fact also follows from the a6rmative solution of Wagner’s conjecture proved by Robertson and Seymour [22]. There are several papers proving directly the Nniteness of irreducible triangulations [2,3,9], by bounding the number of vertices of them. The following result gives the best bound for it in the present. Theorem 5 (Nakamoto and Ota [13]). Let F2be a non-spherical closed surface with Euler characteristic (F2)¡2, and rbe the Euler genus of F2(i.e.,r=2−(F2)). If Gis an irreducible triangulation of F2,then |V(G)|6171r−72: Contraction of an edge in an outer-triangulation is deNned only for outer edges. See Fig. 3. (If we contract an inner edge, then the boundary of the outer face will be deformed into a closed walk which is not a cycle.) We say that an outer edge eis contractible if its contraction yields a simple graph. We also say that an outertriangulation Gis contractible to an outer-triangulation Tif Gcan be transformed into Tby a sequence of contractions of outer edges. An outer-triangulation Gwith no contractible outer edge is said to be irreducible. 68 C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 Fig. 4. Inserting mvertices of degree 3. Lemma 6. For any closed surface,there exist only ;nitely many irreducible outertriangulations,up to homeomorphism. In order to prove Lemma 6, we need the following lemma shown in [6]. Lemma 7. Let Gbe an outer-triangulation on a closed surface F2.Let ˜ Gbe the triangulation on F2obtained from Gby adding a vertex in the outer face of Gand joining it to all vertices of G.Then,the outer-triangulation Gis irreducible if and only if the triangulation ˜ Gis irreducible. Now we prove Lemma 6. Proof of Lemma 6. Combining Theorem 5 and Lemma 7, if Gis an irreducible outertriangulation on a closed surface F2, then |V(G)|6(171r−72) −1 = 171r−71:Thus, the proposition follows. Let Gbe an outer-triangulation on a closed surface F2and let xyz be a face of G such that xy is an outer edge. Subdividing xy by a single vertex vand adding an edge vz, we obtain an outer-triangulation Gwith |V(G)|=|V(G)|+1. In this case, we say that Gis obtained from Gby inserting a vertex of degree 3 on xy. Lemmas 8 and 9 have already been proved in [5,6]. Lemma 8. Let Gbe an outer-triangulation on a closed surface F2with boundary C, and let e; e∈E(C). Let Ge(resp.,Ge)be the outer-triangulation on F2obtained from Gby inserting a vertex of degree 3on e(resp.,e). Then,Geand Geare equivalent to each other,up to isotopy. Let G+mdenote the outer-triangulation obtained from Gby adding mvertices of degree 3, as shown in Fig. 4. By Lemma 8, since we can move an inserted vertex of degree 3 to any outer edge by diagonal ips, any two outer-triangulations with the notation G+mcan be transformed into each other by diagonal ips (i.e., independent of the choice of the edges subdivided by the mvertices of degree 3). C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 69 Fig. 5. Strip extension along e. Lemma 9. Let Gand Tbe two outer-triangulations on a closed surface F2.If G is contractible to T,then Gcan be transformed into T+m,up to isotopy,by a sequence of diagonal +ips,where m=|V(G)|−|V(T)|. 4. From outer-pseudo-triangulations to outer-triangulations In this section, we show how to use the equivalence of outer-pseudo-triangulations described in Section 2. Let Pbe an outer-pseudo-triangulation on a closed surface F2with boundary C. Let e=uv be an inner edge of P. We consider the following operation for P.We now regard the outer face of Pas a hole of F2(i.e., we regard Cas the boundary of the surface). We denote the punctured surface with boundary Cby ˜ F2. Now cut ˜ F2 along e=uv from vto u, and denote the right- and left-side images of eby eRand eL, respectively (then the resulting surface has the boundary C∪eR∪eL, which might be disconnected). Suppose that eR(resp., eL) starts from a vertex vR(resp., vL) and terminates in a vertex uR(resp., uL). Join vRand vLby a path vRvvLof length 2, join uRand uLby a path uRuuLof length 2, and add an edge vu. Regarding each of the 4-cycles vRuRuvand vuuLvLas a quadrilateral region, we Nnally add two diagonals uLvand uvR(as shown in Fig. 5), or uvLand uRv. In particular, if eis a self-incident edge, then by Lemma 3, we may assume that uL=vRand vL=uR.In this case, we add diagonals vLuand vuR, not to make multiple edges between vand uLand between vand uL. Here, uL=vRand vL=uRdo not happen simultaneously, and hence we can add these diagonals without breaking the simpleness of graphs. Clearly, the resulting embedding is also an outer-pseudo-triangulation on F2.We call this operation the strip extension along e. We call the union of the two quadrilateral regions the strip, denoted ˜e, corresponding to e, and call each of eRand eLthe brim of the strip. Let Pbe an outer-pseudo-triangulation on a closed surface F2. Apply the strip extensions for all inner edges of P. We call the resulting outer-pseudo-triangulation the brick graph of P, and denote it by B(P). 70 C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 Lemma 10. Given an outer-pseudo-triangulation Pon a closed surface F2,the brick graph B(P)is an outer-triangulation (i.e.,simple). Proof. By construction, it is clear that any edge in a strip except brims is neither a loop nor multiple edges. So, consider a brim in a strip ˜ecoming from an edge e=uv of Gand Nrst suppose that it is a loop in B(G). Then, eis also a loop at a vertex u=vin G. If the two ends of eare not consecutive in the rotation around u=v, then the strip extension along edges between the two ends of esplit u=vinto two or more distinct vertices and neither eLnor eRcan be a loop in B(G), a contradiction. On the other hand, if there is no edge between the two ends of earound u=v, the loop e must be 1-sided; otherwise, it would bound a monogonal face. In this case, the two edges eLand eRform together a path of length 2 and both of them are not a loop in G, a contradiction again. Since even in this case, we can add diagonals not to make multiple edges as described in the deNnition of the strip extension, B(G) has no loop. Now suppose that B(G) includes a pair of multiple edges, which are brims coming from two edges e1and e2of G. Then e1and e2also form a pair of multiple edges between uand vin G. As well as a loop, strip extension cannot transform them into a pair of multiple edges in B(G) unless their ends form consecutive pairs in the rotations around uand vand unless e1and e2form a 2-sided 2-cycle. However, in the exceptional case, the 2-cycle e1∪e2would bound a diagonal face, a contradiction. Thus, B(G) has no multiple edges. Lemma 11. Let Gbe an outer-triangulation on a closed surface F2.Then,the brick graph B(G)is contractible to G. Proof. Let ebe an inner edge of G. The outer-triangulation obtained from Gby a strip extension along eis clearly contractible to G. Thus, the lemma follows. Let Gand Gbe two outer-triangulations on the same closed surface F2. When Gand Gare equivalent to each other, up to isotopy, keeping the simpleness of graphs, then we simply denote G∼G. Combining Lemmas 9 and 11, we have the following: Lemma 12. Let F2be a closed surface with Euler characteristic (F2), and let Gbe an outer-triangulation on F2.Then, B(G)∼G+4(|V(G)|−3(F2)+3): Proof. By Euler’s formula, we have |E(G)|=2|V(G)|−3(F2)+3. Thus, the number of inner edges of Gis equal to |E(G)|−|V(G)|=|V(G)|−3(F2)+3: Since each strip extension increases the number of vertices by four, we have |V(B(G))|−|V(G)|=4(|V(G)|−3(F2)+3): C. Cort es et al. / Discrete Mathematics 254 (2002) 63–74 71 Fig. 6. A sequence of diagonal ips from B(P)+4. Since B(G) is contractible to G, we have B(G)∼G+4(|V(G)|−3(F2)+3),by Lemmas 9 and 11. Lemma 13. Let Pand Pbe two outer-pseudo-triangulations on a closed surface F2such that Pcan be obtained from Pby +ipping one edge. Then,two outertriangulations B(P)+4and B(P)+4are equivalent. Proof. Let Q=abcd be a quadrilateral in Pformed by two triangular faces abd and bcd. Suppose that the edge bd is ipped to obtain P. Since strip extensions to construct B(P) and B(P) are performed along the inner edges in Pand P, the proof naturally falls into four cases, depending on the number of inner edges on the cycle abcd, but we shall show the lemma only when every edge in Qis an inner edge because the remaining cases may be handled in the same way. See Fig. 6. We label the vertices of B(P) corresponding to a; b; c and das in the Ngure. The left-hand Ngure represents the local structure of B(P)+4corresponding to the face abcd in P. By Lemma 8, we may suppose that a2;a 3and c3;c 4are the inserted vertices of degree 3. By Theorem 4, we do not apply any diagonal ip of a self-incident edge, and hence we may suppose that the faces abd and bcd are diUerent in P. Thus, the vertices a1;:::;a 5;b 1;:::;b 5;c 1;:::;c 5;d 1;:::;d 5are all distinct. Thus, the sequence of diagonal ips transforming the left-hand Ngure into the right-hand Ngure keeps the simpleness of graphs. From the right-hand Ngure, applying diagonal ips in the region bounded by a2a3a4b4b3b2and the region bounded by d2d3d4c4c3c2, we can put edges a2biand b4aifor i=2;3;4 and edges d2ciand c4difor i=2;3;4. The resulting graph can easily be transformed into B(P)+4, similarly to the sequence from the left-hand to the right-hand in Fig. 6. Lemma 14. Let F2be a closed surface with Euler characteristic (F2), and let Gand Gbe any two outer-triangulations on F2with the same number of