An algorithm that constructs irreducible triangulations of once-punctured surfaces

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 An algorithm that constructs irreducible triangulations of once-punctured surfaces M. J. Chávez∗1, S. Lawrencenko†2, J. R. Portillo‡1, and M. T. Villar§1 1Universidad de Sevilla, Spain 2Russian State University of Tourism and Service, Lyubertsy, Moscow Region, Russia Abstract A triangulation of a surface is irreducible if there is no edge whose contraction produces another triangulation of the surface. In this work we propose an algorithm that constructs the set of irreducible triangulations of any surface with precisely one boundary component. Introduction and terminology We restrict our attention to the following objects: •S=Sgor Nkis the closed orientable surface Sgof genus gor closed nonorientable surface of nonorientable genus k. In particular, S0and S1are the sphere and torus, N1and N2are the projective plane and the Klein bottle (respectively). •S−Dis Sminus an open disk D(the hole). This compact surface is called the once-punctured surface. We assume that the boundary ∂S of S, which is equal to ∂D, is homeomorphic to a circle. We use the notation Σwhenever we assume the general case - that is, Σ∈ {S, S −D}. If a (finite, undirected, simple) graph Gis 2-cell embedded in Σ, the components of Σ−Gare called faces. A triangulation of Σwith graph Gis a 2-cell embedding T:G→Σin which each face is bounded by a 3-cycle (that is, a cycle of length 3) of Gand any two faces are either disjoint, share a single vertex, or share a single edge. We denote by V=V(T), E=E(T), and F=F(T)the sets of the vertices, the edges, and the faces of T, respectively. Equivalently, the triangulation Tof a surface can be defined as a hypergraph of rank 3 or a 3-graph, with the vertex set V(T)and the collection F(T)of triplets of V(T) (called 3-edges, or triangles, of T) (see [4]). By G(T)we denote the graph (V(T), E(T)) of triangulation T. Two triangulations T1and T2are called ∗Email: mjchav[email protected]. Research supported by PAI FQM- 189 †Email: lawrencenk[email protected]. ‡Email: [email protected]. Research supported by PAI FQM-164 §Email: [email protected]. Research supported by PAI FQM-164 isomorphic, denoted T1∼ =T2, if there is a bijection α:V(T1)→V(T2)such that uvw ∈F(T1)if and only if α(u)α(v)α(w)∈F(T2). Throughout this paper we distinguish triangulations only up to isomorphism. In the case Σ = S−Dlet ∂T, which is equal to ∂D, denote the boundary cycle of T. The vertices and edges of ∂T are called boundary vertices and boundary edges of T, respectively. A triangulation of a punctured surface is irreducible (term which is more accurately defined in Section 1) if no edge can be shrunk without producing multiple edges or changing the topological type of the surface. The irreducible triangulations of Σform a basis for the family of all triangulations of Σ, in the sense that any triangulation of Σcan be obtained from a member of the basis by applying the splitting operation (introduced in Section 1) a finite number of times. To have such a basis in hand can be very useful in practical application of triangulation generating; the papers [6] and [19] are worth mentioning. It is known that for every surface Σthe basis of irreducible triangulations is finite (the case of closed surfaces is proved in [2], [13], [12], and [7] and the case of surfaces with boundary is proved in [3]). At present such bases are known only for seven closed surfaces and two once-punctured surfaces: the sphere ([14]), projective plane ([1]), torus ([8]), Klein bottle ([9] and [15]), S2,N3, and N4([16, 17]), the disk and Möbius band ([5]). In this paper we present an algorithm which is designed as an application of some recent advances on the study of irreducible triangulations of oncepunctured surface collected in [5]. Specifically, Lemmas 1-3 (in Section 1) are the main supporting theoretical results for the mentioned algorithm. As a particular example, all the non-isomorphic combinatorial types (293 in number) of triangulations of the once-punctured torus are determined. 1 Previous results Let Tbe a triangulation of Σ. An unordered pair of distinct adjacent edges vu and vw of Tis called 43 An algorithm that constructs irreducible triangulations of once-punctured surfaces acorner of Tat vertex v, denoted by hu, v, wi (=hw, v, ui). The splitting of a corner hu, v, wi, denoted by sphu, v, wi, is the operation which consists of cutting Topen along the edges vu and vw and then closing the resulting hole with two new triangular faces, v0v00uand v0v00w, where v0and v00 denote the two images of vertex vappearing as a result of cutting. Under this operation, vertex vis extended to the edge v0v00 and the two faces having this edge in common are inserted into the triangulation; therefore the order increases by one and the number of edges increases by three. If a corner hu, v, wiis composed of two edges vu and vw neighboring around vertex v, sphu, v, wiis equivalent to the stellar subdivision of the face uvw. Especially in the case {Σ = S−D, uv ∈ E(T),and v∈V(T)}, the operation sphu, v]of splitting a truncated corner hu, v]produces a single triangular face uv0v00, where v0v00 ∈E(∂(sphu, v](T))). Under the inverse operation, shrinking the edge v0v00, denoted by shiv0v00h, this edge collapses to a single vertex v, the faces v0v00uand v0v00wcollapse to the edges vu and vw, respectively. Therefore sphu, v, wi ◦ shiv0v00h(T) = T. It should be noticed that in the case {Σ = S−D, v0v00 ∈E(∂T)}, there is only one face incident with v0v00, and only that single face collapses to an edge under shiv0v00h. Clearly, the operation of splitting doesn’t change the topological type of Σif Σ∈ {S, S −D}. We demand that the shrinking operation must preserve the topological type of Σas well; moreover, multiple edges must not be created in a triangulation. A 3-cycle of Tis called nonfacial if it doesn’t bound a face of T. In the case in which an edge e∈E(T)occurs in some nonfacial 3-cycle, if we still insist on shrinking e, multiple edges would be produced, which would expel shieh(T)from the class of triangulations. An edge eis called shrinkable or a cable if shieh(T)is still a triangulation of Σ; otherwise the edge is called unshrinkable or a rod. The subgraph of G(T)made up of all cables is called the cable-subgraph of G(T). The impediments to edge shrinkability in a triangulation Tof a punctured surface S−Dare identified in [2, 3, 1, 8]; an edge e∈E(T)is a rod if and only if esatisfies one of the following conditions: (1) eis in a nonfacial 3-cycle of G(T). In particular, eis a boundary edge in the case in which the boundary cycle is a 3-cycle. (2) eis a chord of D-that is, the end vertices of e are in V(∂D)but e /∈E(∂D). From now on, we assume that S6=S0and make an agreement that by “non-facial 3-cycle” we mean a non-null-homotopic 3-cycle whenever we refer to conditions (1) and (2). Therefore, an edge eis a rod provided eoccurs in some non-null-homotopic 3-cycle, and eis a cable otherwise. Especially, the boundary edges of stellar subdivided faces are now regarded as cables unless they occur in some non-null-homotopic 3-cycles. The convenience of this agreement is that once a rod turns into a cable in the course of any splitting sequence, it always remains a cable under forthcoming splittings. A triangulation is said to be irreducible if it is free of cables or equivalently, each edge is a rod. For instance, a single triangle is the only irreducible triangulation of the disk S0−D. Let Tbe an irreducible triangulation of a punctured surface S−Dwhere S6=S0. Let us close the hole in Tby restoring the disk Dadd a vertex, p, in D, and join pto the vertices in ∂D. We thus obtain a triangulation, T∗, of the closed surface S. In this setting we call Dthe patch, call pthe central vertex of the patch, and say that Tis obtained from the corresponding triangulation T∗of Sby the patch removal. Notice that T∗may be an irreducible triangulation of Sbut not necessarily. Using the assumption that Tis irreducible and the fact that each cable of T∗ fails to satisfy condition (1) (in the strong non-null- homotopic sense), it can be easily seen that in the case T∗is not irreducible, all cables of T∗have to be entirely in D∪∂D and, moreover, there is no cable which is entirely in ∂D whenever the length of the boundary cycle ∂D is greater than or equal to 4. In particular, we observe that each chord of D(if any) is a rod in Tbecause it meets condition (2), and is also a rod in Tbecause it meets condition (1). We now come to a lemma which is to be stated shortly after some necessary definitions. A vertex of a triangulation Rof Sis called a pylonic vertex if that vertex is incident with all cables of R. A triangulation which has at least one cable and at least one pylonic vertex is called a pylonic triangulation. A triangulation may have a unique cable and therefore two pylonic vertices. However, if the number of cables in a pylonic triangulation Ris at least 2, Rhas exactly one pylonic vertex. Lemma 1 Suppose an irreducible triangulation Tof a punctured surface S−D(S6=S0) is obtained from the corresponding triangulation T∗of Sby the patch removal. If T∗has at least two cables, then either the central vertex pof the patch is the only pylonic vertex of T∗, or else the length of ∂D is equal to 3. Let Ξn= Ξn(S)denote the set of triangulations of a fixed closed surface Sthat can be obtained from an irreducible triangulation of Sby a sequence of exactly nrepeated splittings. In the following result, by the “removal of a vertex v” we mean the removal of vtogether with the interiors of the edges and faces incident with vand by the “removal of a face” we mean the removal of the interior of that face. 44 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Lemma 2 Each irreducible triangulation Tof S−D (S6=S0) can be obtained either (i) by removing a vertex from a triangulation in Ξ0= Ξ0(S), or (ii) by removing a pylonic vertex from a triangulation in Ξ1∪Ξ2∪ · · · ∪ ΞK, where the constant Kis provided by [3] (whenever a pylonic triangulation occurs), or (iii) by removing either of the two faces containing a cable in their boundary 3-cycles provided that cable is unique in a triangulation in Ξ1(whenever such a situation occurs), or (iv) by removing the face containing two, or three, cables in its boundary 3-cycle provided those two, or three, cables collectively form the whole cablesubgraph in a triangulation in Ξ1∪Ξ2(if such a situation occurs). Lemma 3 If a triangulation of Shas at least two cables but has no pylonic vertex, then no pylonic vertex can be created under further splitting of the triangulation. 2 Sketch of the algorithm In this section triangulations are considered to be hypergraphs of rank 3 or 3-graphs. Let Tbe a 3- graph with V=V(T)and F=F(T)the sets of the vertices and the triangles of T. This 3- graph can be uniquely represented as a bipartite graph BT= (V(BT), E(BT)) in the following way: V(BT) = V(T)∪F(T),uv ∈E(BT)if and only if the vertex ulies in the triangle vin T. The algorithm input is the set Iof irreducible triangulations of a closed surface S6=S0. The output of the algorithm is the set of all non-isomorphic combinatorial types of irreducible triangulations of the once-punctured surface S−D. The first step is the generation of the set Ξ1∪Ξ2 from the set I. Next, every 3-graph T∈Ξ1∪Ξ2 is then represented by their corresponding bipartite graph BT. This has been implemented with the computational package Mathematica ([18]). The second step consists of discarding all duplicate bipartite graphs and then, all duplicate triangulations in Ξ1∪Ξ2will be discarded. That is, the obtention of all non-isomorphic triangulations, denoted f Ξ1∪ f Ξ2re- spectively, which is implemented with the computing packages Nauty (and gtools, [10], [11]). Next, all pylonic vertices in f Ξ1∪ f Ξ2are detected and operations (i)–(iv) described in Lemma 2 are applied to obtain irreducible triangulations (using Mathematica). If Ξ2has no pylonic triangulation, immediately proceed to the final step: Discard all duplicate triangulations by using Nauty and gtools. Otherwise generate Ξ3and apply the preceding steps to Ξ3. Repeat this procedure to process Ξ4,Ξ5, . . . until no pylonic triangulation is left in the current Ξn; then the process terminates and a required output is produced. The validity of this procedure is justified by Lemmas 1 - 3 along with the results of [3]. In particular, the finiteness of the procedure is deduced from the upper bound [3] on the number of vertices in an irreducible triangulation of S−D. In particular, that upper bound implies (along with Lemma 3) that Ξndoes not have a pylonic triangulation for any n≥K+ 1, where K= 945 for S1and K= 376 for N1. In reality Kis much less than these values. By computer verification (and also by hand) we have checked that in fact K= 1 for S1, and K= 2 for N1. Let us now mention two examples. Firstly, this algorithm has been implemented for the set of two irreducible triangulations of N1([1]). The algorithm gives a set of 6 irreducible triangulations of the Möbius band, N1−D, which is precisely the same as that obtained by some of the authors of this work in [5], although by using no computational package. Secondly, we introduce the details of the torus case, S1. Example: the once-punctured torus Input: The set of 21 irreducible triangulations of S1 (as they are labelled in [8]). •Ξ1(S1)has 433 non-isomorphic triangulations: 232 of them have no pylonic vertex, 193 have an only pylonic vertex and 8 have two pylonic vertices. •Ξ2(S1)has 11612 non-isomorphic triangulations, none of them is a pylonic triangulation. •Operations described in Lemma 2 provide: (i) 184 triangulations; only 80 of them are nonisomorphic. (ii) 209 triangulations; only 203 of them are non-isomorphic. (iii) 16 triangulations, 10 of them are nonisomorphic. (iv) 0 triangulations. Output: 293 non-isomorphic combinatorial types of irreducible triangulations of the once-punctured torus S1−D. 3 Final conclusion It is clear that this algorithm can be implemented for any closed surface whenever its basis of irreducible 45 An algorithm that constructs irreducible triangulations of once-punctured surfaces triangulations is known. In a future contribution we hope to present the set of irreducible triangulations of the once-punctured Klein bottle, N2−D. References [1] D. Barnette (D. W. Barnette). Generating the triangulations of the projective plane. J. Comb. Theory, Ser. B,33, (1982), 222–230. [2] D. W. Barnette, A. L. Edelson. All 2-manifolds have finitely many minimal triangulations. Isr. J. Math., 67, (1989), No. 1:123–128. [3] A. Boulch, É. Colin de Verdière, A. Nakamoto. Irreducible triangulations of surfaces with boundary. Graphs and Combinatorics DOI 10.1007/s00373-012- 1244-1, 2012. [4] J. Bracho, R. Strausz, Nonisomorphic complete triangulations of a surface. Discrete Math. 232, (2001), 11–18. [5] M. J. Chávez, S. A. Lawrencenko, A. Quintero, M. T. Villar. Irreducible triangulations of the Möbius band. Preprint 2013. [6] L. Giomi, M. J. Bowick. Elastic theory of defects in toroidal crystals. Eur. Phys. J. E.,27, (2008), 275– 296. [7] G. Joret, D. R. Wood. Irreducible triangulations are small. J. Comb. Theory, Ser. B,100, (2010), No. 5:446–455. [8] S. A. Lavrenchenko (S. Lawrencenko). Irreducible triangulations of the torus. J. Sov. Math.,51, No. 5 (1990), 2537–2543; translation from Ukr. Geom. Sb. 30, (1987), 52–62. [9] S. Lawrencenko, S. Negami. Irreducible triangulations of the Klein bottle. J. Comb. Theory, Ser. B, 70, No. 2 (1997), 265–291. [10] B. McKay, Practical Graph Isomorphism. Congressus Numerantium,30, (1981), 45–87. [11] B. McKay, nauty User’s Guide (Version 2.4) http://pallini.di.uniroma1.it/ [12] A. Nakamoto, K. Ota. Note on irreducible triangulations of surfaces. J. Graph Theory,20, (1995), No. 2:227–233. [13] S. Negami. Diagonal flips in pseudo-triangulations on closed surfaces. Discrete Math.,240, (2001), No. 1– 3:187–196. 2001. [14] E. Steinitz, H. Rademacher, Vorlesungen über die Theorie der Polyeder unter Einschluss der Elemente der Topologie. Berlin: Springer, 1976. [Reprint of the original 1934 edition.] [15] T. Sulanke. Note on the irreducible triangulations of the Klein bottle. J. Comb. Theory, Ser. B,96, No. 6, (2006), 964–972. [16] T. Sulanke. Generating irreducible triangulations of surfaces, preprint, 2006, arXiv:math/0606687v1 [math.CO]. [17] T. Sulanke. Irreducible triangulations of low genus surfaces, preprint, 2006, arXiv:math/0606690v1 [math.CO]. [18] Wolfram Research, Inc. Mathematica Version 8.0 (Wolfram Research, Inc.) Champaign, Illinois 2010. [19] Y. Zhongwey, J. Shouwei. STL file generation from digitised data points based on triangulation of 3D parametric surfaces.Int. J. Adv. Manuf. Technol. 23, (2004), 882–888. 46