Geometric Realization of Möbius Triangulations

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. SIAM J. DISCRETE MATH.c 2008 Society for Industrial and Applied Mathematics Vol. 23, No. 1, pp. 221–232 GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS∗ MAR´ IA JOSE CH´ AVEZ†,GA ˇ SPER FIJAVˇ Z‡,ALBERTOM ´ ARQUEZ†, ATSUHIRO NAKAMOTO§,AND ESPERANZA SU´ AREZ† Abstract. AM¨obius triangulation is a triangulation on the M¨obius band. A geometric realization of a map Mon a surface Σ is an embedding of Σ into a Euclidean 3-space R3such that each face of Mis a flat polygon. In this paper, we shall prove that every 5-connected triangulation on the M¨obius band has a geometric realization. In order to prove it, we prove that if Gis a 5-connected triangulation on the projective plane, then for any face fof G,theM¨obius triangulation G−f obtained from Gby removing the interior of fhas a geometric realization. Key words. geometric realization, triangulation, M¨obius band, projective plane AMS subject classifications. 05C10, 52B70, 05C83 DOI. 10.1137/070693382 1. Introduction. Let Σ be a surface with at most one boundary component, and let Mbe a map on Σ. If Σ has a boundary, we suppose that some cycle of M coincides with the boundary of Σ. Such a cycle of Mis called the boundary of M and denoted by ∂M.AvertexofMnot on ∂M is called an inner vertex. A k-cycle means a cycle of length k.Atriangulation onΣisamaponΣsuchthateachfaceis bounded by a 3-cycle. In particular, a M¨obius triangulation is a triangulation on the M¨obius band. For an inner vertex vof a triangulation, the link of vis the boundary walk of the 2-cell region consisting of all faces incident to v. Throughout this paper, we suppose that the graph of a map is simple, i.e., with no multiple edges and no loops. For a cycle or path Cin M,achord of Cmeans an edge xy of Msuch that x, y ∈V(C) but xy /∈E(C). Hence Cis induced in Mif and only if Chas no chord. Ageometric realization of a map Mon a surface Σ is an embedding of Σ into a Euclidean 3-space R3such that each face of Mis a flat polygon. Steinitz’s theorem states that a spherical map has a geometric realization if and only if its graph is 3-connected [10]. Moreover, Archdeacon, Bonnington, and Ellis-Monanghan proved that every toroidal triangulation has a geometric realization [1]. In general, Gr¨unbaum conjectured that every triangulation on any orientable closed surface has a geometric realization [7], but Bokowski and Guedes de Oliveira recently showed that a triangulation by K12 on the orientable closed surface of genus 6 has no geometric realization [2]. (For related topics, see [5].) Let us consider a geometric realization of a triangulation on the projective plane. Let Pdenote the projective plane throughout this paper. Since the projective plane itself is not embeddable in R3, no map on Phas a geometric realization. Let Gbe a triangulation on P,andletfbe a face of G.LetG−fdenote the M¨obius triangulation ∗Received by the editors May 31, 2007; accepted for publication (in revised form) August 22, 2008; published electronically December 19, 2008. http://www.siam.org/journals/sidma/23-1/69338.html †Departamento de Matematica Aplicada I, Universite de Sevilla, Escuela Universitaria Arquitectura Tecnica, Avda Reina Mercedes S/N, 41012 Sevilla, Spain ([email protected], [email protected], [email protected]). ‡Department of Computer Science, University of Ljubljana, 1000 Ljubljana, Slovenia (gasper. fi[email protected]-lj.si). §Department of Mathematics, Yokohama National University, Yokohama 240-8501, Japan ([email protected]). 221 Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 222 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ 123 31 4 7 54 7 5 8 9 6 8 8 7 7 9 9 4 65 12 3 Fig. 1.AM¨obius triangulation with no geometric realization. obtained from Gby removing the interior of f. Since the punctured surface obtained from Pby removing a 2-cell, the M¨obius band, is embeddable in R3,G−fmight have a geometric realization. The following is known. Theorem 1.1 (Bonnington and Nakamoto [3]). Every triangulation Gon the projective plane Phas a face fsuch that the M¨obius triangulation G−fhas a geometric realization. Brehm [4] has already found a M¨obius triangulation with no geometric realization, shown in Figure 1, in which both express the same triangulation. (In Figure 1, we identify the vertices with the same label. In the right-hand side, the shaded part means the hole.) Why does Brehm’s example have no geometric realization? We can prove that for each of its spatial embedding, the two disjoint 3-cycles 123 and 456 have a linking number of at least 2. (See [9] for the definition of the linking number.) However, two 3-cycles, each with an edge straight segment embedded in R3,havea linking number of at most 1, a contradiction. Hence, generalizing this example, we can see that if a triangulation Mon the M¨obius band has a boundary cycle Cof length 3anda3-cycleCdisjoint from Cwhich forms an annular region with C,thenM never has a geometric realization. AgraphMis said to be cyclically k-connected if Mhas no separating set S⊂ V(M)with|S|≤k−1 such that each connected component of M−Shas a cycle. Then the cyclical 4-connectivity of a triangulation Gon Pis necessary for a geometric realization of G−ffor any face fof G. We conjecture as follows that it is also sufficient. Conjecture 1.2. Let Gbe a triangulation on the projective plane P.Then G−fhas a geometric realization for any face fof Gif and only if Gis cyclically 4-connected. In this paper, we prove the following. Theorem 1.3. Let Gbe a 5-connected triangulation on the projective plane P. Then G−fhas a geometric realization for any face fof G. By Theorem 1.3, a M¨obius triangulation Mhas a geometric realization if Mis obtained from a 5-connected triangulation Gon Pby removing a 2-cell. Let Mbe a 5-connected M¨obius triangulation with a boundary cycle C=v1···vk of length k.LetPbe the map on Pobtained from Mbypastinga2-celltoC.Ifk=3, then Pis a 5-connected triangulation on P.Ifk=4,thenPcanbeextendedtoa5- connected triangulation on Pby adding an edge v1v3or v2v4. (If this is impossible, then Mwould have edges v1v3and v2v4, and hence Mwould contain a quadrangulation Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 223 isomorphic to K4, contrary to the 5-connectivity of M.) If k≥5, then Pcan be extended to a 5-connected triangulation on Pby adding a new vertex joined to all vertices on C. Hence we have the following. Corollary 1.4. Every 5-connected M¨obius triangulation has a geometric realization. Let Mbe a map on a surface Σ with a boundary, and let Cbe the boundary cycle of M.WesaythatMis internally k-connected if Mis (k−1)-connected and if for any vertex v∈V(M−C), there are at least kdisjoint paths from vto C. Clearly, if Gis a 5-connected triangulation on P, then for any v∈V(P), G−vcan be regarded as an internally 5-connected M¨obius triangulation whose boundary cycle has a length of at least 5. Hence we can relax the condition of Corollary 1.4 to prove the following. Corollary 1.5. Every internally 5-connected M¨obius triangulation has a geometric realization if the boundary cycle has a length of at least 5. 2. Split-K5’s in 5-connected triangulations. Put a 5-cycle C=v1v2v3v4v5 on P, called the boundary,sothatCbounds a 2-cell Ron P,whereeachviis called anode. (We always fix its orientation  Calong the numbering of the vertices.) Join vi to vi+2 and vi+3 by edges not in Rfor each i. Then the resulting graph is isomorphic to K5in which each face except Ris triangular. (See the left-hand side of Figure 2.) Consider a splitting (i.e., the inverse operation of an edge contraction) of viinto two adjacent vertices, viand v i, of degree 3. There are two possibilities for the splitting. When viand v ilie on C(we always suppose that viand v iappear on  Cin this order), {vi,v i}is called a boundary pair of nodes, and each of viand v iis called a boundary split node.(Thepathfromvito v ion  Cis called the boundary split interval of {vi,v i}.) Otherwise, {vi,v i}is called an inner pair of nodes, and each of viand v i is called an inner split node, where we always suppose that vilies on C.LetKbe a map on Pobtained from the above K5by splittings of some of vi’s. A split-K5is a subdivision of Kon P. (See the right-hand side of Figure 2.) v0v1v2v3 v3v4v0 v0v1v2v3 v3v4v0 K5Split-K5 v 1 v 2 v 3 v 3 Inner pair Boundary pair Fig. 2.K5and split-K5. The following is the most important claim in this paper. It guarantees that a 5-connected triangulation on Phas a special type of a split-K5. Lemma 2.1. Let Gbe a 5-connected triangulation on P,andletuvw be any face of G.ThenGhas a split-K5Hsuch that (i) the boundary ∂H of Hcoincides with the link of uin G. (ii) Hhas at most one boundary pair of nodes. (iii) if Hhas a boundary pair, then at least one of vand wis a boundary split node, but the edge vw is not contained in a boundary split interval. Otherwise, vor wis a node of H. Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 224 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ In the following two sections, we give preliminaries for the proof of Lemma 2.1. In section 5, we prove Lemma 2.1. 3. Lemmas. Let Gbe a graph on P,andletCbe a contractible cycle of G, i.e., one bounding a 2-cell on P. (A cycle or a closed curve on a surface is essential if it is not contractible.) Then Ccuts Pinto two surfaces, one homeomorphic to an open disk and the other homeomorphic to an open M¨obius band. Let intC(G)denotethe graph consisting of the vertices and edges lying in the disk component of C,andlet IntC(G) be the graph consisting of the vertices and edges lying on Cand in the disk component of C. We define extC(G)andExt C(G) analogously. Note that IntC(G)is not necessarily an induced subgraph of G. Let C=v1v2v3v4···vkbe a cycle. A closed segment [vi,v j]isavi−vjpath along  C.Anopen segment (vi,v j) is obtained by deleting the endvertices of the corresponding closed segment. Moreover, we use the notations [vi,v j)and(vi,v j], defined similarly. Lemma 3.1. Let Gbe a 5-connected triangulation on P.LetC=v1v2v3v4be a contractible 4-cycle in G.ThenintC(G)contains no vertices. Proof. Assume v∈V(intC(G)). Since Gis 5-connected, extC(G)containsno vertices. Then we can add only two edges v1v3and v2v4outside C,sinceTis simple. Hence this contradicts that Gis a triangulation. Lemma 3.2. Let vbe a vertex of a 5-connected triangulation Gon P,andlet Cbe a contractible 5-cycle containing vin its interior. Then there exists a unique contractible 5-cycle Cso that IntC(G)contains all contractible 5-cycles which contain vin their respective interiors. Proof.LetC1and C2be contractible 5-cycles containing vin their interiors, and suppose that IntC1(G)andInt C2(G)areinclusionwise incomparable, that is, neither IntC1(G)⊆IntC2(G)norInt C1(G)⊇IntC2(G). It suffices to prove that there is a contractible 5-cycle Csuch that IntC(G) contains both IntC1(G)andInt C2(G). Since C1and C2are of length 5 and neither one is contained in the closed interior of the other, they intersect in exactly two vertices. These two vertices divide Ciinto a segment lying in the interior of C3−iand one lying in the exterior of C3−i,wherei= 1,2. Combining the common segments and both interior segments yields a contractible cycle, which contains vin its interior. By Lemma 3.1, its length is at least 5. Combining the two exterior segments with the two common segments, we obtain a contractible cycle Cof length at most 5, since both C1and C2were 5-cycles. Since Gis simple, Ccontains no essential cycle, and hence it is a contractible cycle in G.NowChas length 5 by Lemma 3.1 since it contains vin its interior. On the other hand, IntC(G) contains both IntC1(G)andInt C2(G), and the proof is complete. Lemma 3.3. Let Gbe a 5-connected triangulation on P,andletC=v1v2v3v4v5 be a contractible 5-cycle in G.IfGhas no vertex in the exterior of C,thenExtC(G) is isomorphic to K5. Proof. We have to show that extC(G) contains every possible edge vivi+2 (in indices modulo 5). A similar argument as in the proof of Lemma 3.1 does the trick. The following lemma is an immediate consequence of 5-connectivity. Lemma 3.4. Let Gbe a 5-connected triangulation on P,andletv∈V(G).Let vand v be two nonconsecutive neighbors of v.Ifvand v have another common neighbor wwhich is not adjacent to v, then the cycle vvwv is essential. Let Dbe a plane graph with boundary cycle Cand each inner face triangular, and let x, y be distinct vertices of C.Aninternal x−ypath is a path in Djoining x and yand intersecting Conly at its endvertices. Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 225 Lemma 3.5. Let Dbe a triangulation on the disk with boundary cycle C,andlet x, y be distinct vertices of Cwith xy /∈E(C).ThenDhas an internal x−ypath if and only if Dhas no chord pq for some p, q ∈V(D)−{x, y}such that xand yare contained in distinct components of C−{p, q}. Proof. The sufficiency is obvious and so we consider the necessity. Suppose that C has a chord pq. By the assumption, xand yare contained in one, say D1,ofthetwo subgraphs D1,D 2such that V(D)=V(D1)∪V(D2)andV(D1)∩V(D2)={p, q}. In this case, we have to look for a required internal x−ypath in D1. Hence in the following argument, we may suppose that Dhas no chord. Observe that since Cis chordless, each vertex on Cis adjacent to at least one vertex in D−C.Moreover, we can see that intC(D) is connected. (For otherwise, i.e., if intC(D) is disconnected, then there are two vertices p,q∈Csuch that D−{p,q}is disconnected. However, this is impossible since each inner face of Dis triangular.) Hence we have an internal x−ypath in D. Let Cbe a contractible cycle of length at least 4 in a triangulation G. Suppose that vertices r1,r 2,r 3,r 4lie along Cin this order, but they do not need to be consecutive along C. Let us also assume that the segments [r1,r 2], [r2,r 3], [r3,r 4], and [r4,r 1] have no chords in IntC(G). We say that IntC(G)isa4-patch with nodes r1,r 2,r 3,r 4. We obtain the following three lemmas, carefully applying Lemma 3.5 to P. Lemma 3.6. Let Pbe a 4-patch with nodes r1,r 2,r 3,r 4. Assume that r1r4,r 2r3∈ E(P)and that uand vare vertices from (r1,r 2)and (r3,r 4), respectively. Then P− {r1,r 2,r 3,r 4}contains an u−vpath, or a pair of antipodal nodes are adjacent. Lemma 3.7. Let Pbe a 4-patch with nodes r1,r 2,r 3,r 4.ThenP−{r1,r 3}contains an r2−r4path unless r1r3∈E(P). Let Pbe a 4-patch with nodes r1,r 2,r 3,r 4.Anr2−r4diagonal in Pis an r2−r4 path Q=u1u2u3···uk−1uk(u1=r2and uk=r4)inP−{r1,r 3}if there exists indices i<jsuch that (D1) the initial segment u1···uiis a segment of ∂P, (D2) the terminal segment uj···ukis a segment of ∂P,and (D3) the intermediate segment ui···ujis a segment of Psuch that ui,u j∈V(∂P) and that all other vertices lie in int(P). If Qis an r2−r4diagonal in P,thenitisalsoanr4−r2diagonal. Further, if a patch Pwith nodes r1,r 2,r 3,r 4contains an r2−r4path avoiding r1and r3,thenitalso contains an r2−r4diagonal. We say that an r2−r4diagonal Qlies closest to r1if the number of faces of P bounded by Qand the segments incident with r1is as small as possible. Lemma 3.8. Let Pbe a 4-patch with nodes r1,r 2,r 3,r 4,andletQbe the r2−r4 diagonal closest to r1.Letuiand ujbe the first and last vertex of the intermediate segment of Q, respectively. Then r1is adjacent to ui,u i+1,...,u j−1,u jin P. 4. Essential 3-linkages. Anear triangulation Ris a map on Pwith a distinguished face fsuch that every other face of Ris triangular, and that the facial walk along fis a cycle. Suppose that the boundary cycle of f, denoted by W, has a length of at least 6. Let v1,v 2,v 3,v 4,v 5,v 6be six vertices that appear along Win this order but that do not need to be consecutive along W.Anessential 3-linkage (with respect to v1,v 2,v 3,v 4,v 5,v 6) is a collection Lof three disjoint paths P1,P2,P3so that Piis avi−vi+3 path for i=1,2,3. It is easy to see that W∪Picontains some essential cycle. Let Q1be some minimal subpath of P1so that W∪Q1still contains an essential cycle. Also Q1,P 2,P 3form an essential 3-linkage with possibly different endvertices. By applying the same idea on P2and P3, we obtain the following lemma. Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 226 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ Lemma 4.1. Let Lbe an essential 3-linkage with respect to nodes v1,...,v 6. There exists an essential 3-linkage Lso that every path in Lintersects Wonly at its endvertices. The second result has been, in greater generality, proved by Robertson and Seymour in [8]. We state it adapted to our needs. Theorem 4.2 (Robertson and Seymour [8]). Let Rbe a near triangulation of P and f=v1v2v3v4v5v6its distinguished face of length 6.ThenRcontains an essential 3-linkage with respect to v1,v 2,v 3,v 4,v 5,v 6if and only if (L1) Rcontains no pair of parallel nonhomotopic edges with common endvertices; (L2) Rdoes not contain a contractible cycle Cof length at most 5whose interior contains f. A pair of parallel nonhomotopic edges violating (L1) forms an essential cycle of length 2. Traversing these two edges twice yields a contractible (but not simple) closed walk whose “interior” contains all faces of R. This observation enables both conditions (L1) and (L2) to be combined into a single condition, albeit with slight adaptations. For practicality, we prefer the conditions to be written separately, since they are of different flavors and have to be tackled with different approaches. We look for essential 3-linkages in near triangulations. In the case when the length of the distinguished face exceeds 6, we first decide which six vertices are the endvertices of a linkage. The rest of this section is devoted to the proof of the following. Proposition 4.3. Let Gbe a 5-connected triangulation of P,andletvbe a vertex of degree d≥6.LetD=u1u2···udbe the link of vin G. Then the near triangulation R=G−vcontains an essential 3-linkage if and only if vis not contained in the interior of a contractible cycle of length at most 5. Proof. Clearly a cycle containing vin its interior meets each path in an essential 3- linkage at least twice. The difficulty lies in the other direction—how to find a linkage— if vis not contained in the interior of a “short” contractible cycle. An edge e∈E(R)issaidtobeessential if the endvertices of elie in Dand D∪e contains an essential cycle. We shall split the proof of Proposition 4.3 with respect to the number of essential edges. If Rcontains a set of three independent essential edges, then no further proof is needed. This leaves us with the case where a maximal set of independent essential edges contains at most two edges. Assume next that Rcontains a set of two independent essential edges. The four endvertices of these essential edges split the f-facial walk into four open segments. Let us choose essential edges e=r1r4and e=r3r6in such a way that the union of two consecutive open segments (r1,r 6)∪(r3,r 4)inDcontains as few vertices as possible. Suppose that (r1,r 3)containsavertex,sayv2,andthat(r4,r 6)containsavertex, say v5.Nowifr1r6∈E(R)−E(D), then the contractible cycle vr4r1r6separates v2 from v5,andifr3r4∈E(R)−E(D), then the contractible cycle vr3r4r1separates v2from v5. Neither can happen since Gis 5-connected. By Lemma 3.6, we can join v2and v5by a path avoiding r1,r 2,r 3,andr4, and hence we can find an essential 3-linkage. So we assume that there exists a set of two independent essential edges e=w1w3 and e=w2w4so that w1,w 2,andw3lie consecutively along D. We may also assume that w4lies closer to w3than to w1along D, and that no essential edge incident with w2has the other endvertex in (w3,w 4). Denote the vertices along Dby v1,v 2,v 3,...,v d so that v1=w1and v2=w2(also v3=w3, but then this may not go on). Add to R the new edges v1vk,wherek=6,...,d−1, and denote the resulting near triangulation with R, with the distinguished face of size 6. Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 227 It is easy to see that Rsatisfies (L1), since the newly added edges do not have their essential counterparts. Similarly, a short contractible cycle Ccontaining the distinguished face of Rin its interior, i.e., contradicting (L2), would have to use some new edge v1vk,wherek≥6. Now Cwould contain vertices vk,w 1,w 2,andw3, which implies that vertices vkand w3haveacommonneighborinR. This contradicts Lemma 3.4 since Cis contractible. Hence Rcontains an essential 3-linkage. Since all new edges share a common endvertex, we can, if necessary, transform the linkage into an essential 3-linkage in R. Suppose next that there is an essential edge but we cannot find a set of two independent essential edges. Let e=w1w2be the essential edge, and assume that the segment (w1,w 2) is as short as possible. Since Gis simple, w1and w2are not consecutive along D. Denote the vertices of Dso that w1=v3and v4lies in (w1,w 2). As (w1,w 2) is as short as possible, we have w2=v1. As in the previous case, let Rbe the near triangulation obtained by adding new edges v1vk,wherek=6,...,d−1. We will argue that Rhas an essential 3-linkage. If Rdoes not satisfy (L1), then an essential edge emust be incident with both v1and vkfor some ksatisfying 6 ≤k≤d. By interlacing essential edges incident to vk∈[w1,w 2]=[v3,w 2], we clearly have vk=v3. On the other hand, vkcannot lie in (w1,w 2)=(v3,w 2), as two independent essential edges cannot exist, and hence vk=w2. But this contradicts 5-connectivity of G, since the 4-cycle vv1vkv3=vv1w2w1 separates v2and v4. Next assume that Rcontradicts (L2). The short cycle Ccontradicting (L2) can be divided into three segments: the first one between v1and w1, the second between w1and w2, and the third between w2and v1. Their lengths are at least 2, 2, and 1, respectively, using the fact that neither v1and w1=v3nor w1and w2are consecutive along D, and the fact that Cuses one of the new edges. Since the length of Cis at most 5, all lower bounds are sharp. By Lemma 3.4, Cmust pass through v2,andalso Cmust pass through v4and w2=v5. On the segment between w2and v1the cycle C uses exactly one edge, namely v1w2=v1v5, and it also has to use one new edge. This is a contradiction, so Rsatisfies both (L1) and (L2), and Rcontains an essential 3-linkage. As in the previous case we can, if necessary, transform the linkage into an essential 3-linkage in R. We are left with the case where Rcontains no essential edges. Even if we add new edges to the interior of f, we cannot contradict (L1), and our only concern will be meeting the condition (L2). We proceed naively. Let us assign labels v1,v 2,...,v dto neighbors of vin the order of their indices. Add new edges of the form v1vk,wherek=6,...,d−1. The newly obtained near triangulation Rmay contain an essential 3-linkage, and we win. On the other hand, it may not, as we contradict (L2), and we lose.Inthiscase,R contains a short cycle Cwhich uses a new edge v1vfor some ∈{6,...,d−1}. Hence we assume that we lose for every assignment of labels v1,v 2,...,v dto the consecutive neighbors of v. Now fix an assignment of labels so that there exists a cycle Cvcontradicting (L2) using a new edge v1vk,wherekis as large as possible. Let us denote w1=v1,w2=v2,w3=v3,w4=vk−1,w5=vk,andw6= vk+1. Further, let us add new edges joining w1to vertices of (w6,w 1) and additional new edges joining w3to vertices of (w3,w 4). We denote the newly obtained near triangulation by Rw. We claim that Rwcontains an essential 3-linkage. Assume that this is not the case, and let Cwbe the obstruction according to (L2). Clearly Cwcontains at least one new edge. Observe that Cwcannot contain both a Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 228 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ new edge incident with w1and a new edge incident with w3, since a segment of Cwof length at most 2 would join two nonconsecutive vertices of D. The cycle Cwcannot contain a new edge incident with w1since this would contradict maximality of k. Hence, Cwcontains a new edge incident with w3.NowletCbe the cycle containing the edges of Cwlying outside Cvand the edges of Cvlying outside of Cw.ThenCis a contractible cycle containing fin its interior. Let P⊆Cw∪Cvbe the v1−v3path whose edges lie in the interior of C. Since it connects two nonconsecutive vertices along f, its length is at least 3. This implies that the length of Cis at most 5, a contradiction. Hence Rwcontains an essential 3-linkage, and consequently Ralso contains an essential 3-linkage. This completes the proof of Proposition 4.3. 5. Proof of Lemma 2.1. In this section, we shall prove Lemma 2.1. We begin with the following proposition. Proposition 5.1. Let Gbe a 5-connected triangulation on P,andletu∈V(G). Then Ghas a split-K5Hwhose boundary coincides with the link of uin G. Proof. We will split the analysis into two cases regarding the properties of uand treat one of the two cases by referring to [6]. Let Dbe the link of u. Case 1. Gcontains a contractible 5-cycle C=v1v2v3v4v5such that u∈V(intC(G)). By Lemma 3.2, we may assume that Cis the maximal 5-cycle containing uin its interior. Since Gis 5-connected, there exist internally disjoint u−vipaths Pifor i=1,...,5. In order to find a suitable split-K5, we need to find a subgraph of ExtC(G) which contracts to the zigzag cycle v1v3v5v2v4. This task has been treated in greater generality in [6, subsection: Finding a suitable cycle minor Uin Gx]. Hence we can obtain a split-K5Hwhose boundary is C.Nowlet H=(H−E(C)) ∪D∪ 5  i=1 (Pi−{v}). Then His a split-K5with boundary D, in which there is no boundary pair. Case 2. udoes not lie in the interior of a contractible 5-cycle. Then we clearly have |D|=deg(u)=k≥6. Let fbe the distinguished face of G−vwith boundary D. By Theorem 4.2, G−vcontains an essential 3-linkage L={P1,P 2,P 3}with respect to u1,u 2,u 3,u 4,u 5,u 6,wherePijoins uiand ui+3 for i=1,2,3. We may also assume that each Piin Lhas no chord. Then Ldivides the near triangulation G−vinto three patches R12,R23,andR13, whose nodes are (u1,u 2,u 5,u 4), (u2,u 3,u 6,u 5), and (u3,u 4,u 1,u 6) lying on their boundary in this order, respectively. We first claim that these patches contain two vertex-disjoint diagonals. Let us first prove that every two patches, say R12 and R23, contain diagonals with disjoint endvertices. Suppose this is not the case, and let, say, u2be an endvertex of every possible diagonal in both R12 and R23. By Lemma 3.7, we have u2u4∈E(R12)and u2u6∈E(R23).This contradicts the 5-connectivity of Gsince {u, u2,u 4,u 6}separates v5and v1in G. Hence we may assume that R12 contains a u1−u5diagonal D15 and that R23 contains a u2−u6diagonal D26. We first suppose that D15 and D26 are disjoint. In this case, we can obtain a required split-K5Hsuch that H=D∪L∪D15 ∪D26. Now consider the case when D15 and D26 share an inner vertex. Let us try to push the diagonals away: suppose that D15 and D26 are closest to u4and u3, respectively. If D15 and D26 are not vertex disjoint, then the terminal segment Sof D15 intersects Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 229 the initial segment Sof D26 at P2.Letwbe the first vertex of S,andletwbe the last vertex of S. Then, by Lemma 3.8, we have both u4w∈E(R12)andu3w∈E(R23). If w=w, then we can find a u2−u4diagonal in R12 through wu4and a u3−u5 diagonal in R23 through u3w. Since they are disjoint, we are done, similarly as above. Suppose that w=w.Sinceu4w∈E(R12), we focus on the 4-patch R 12 with nodes u1,u 2,w,u 4contained in R12.Notethatu1w/∈E(R 12). (For otherwise, {u, u1,w,u 3}separates u2and u4,sinceu3w∈E(R23). This contradicts the 5- connectivity of G.) Hence R 12 admits a u2−u4diagonal D24, avoiding wand u1,by Lemma 3.7. Let D35 be the u3−u5diagonal of R23 through u3w.ThenD∪L∪D24∪D35 is a required split-K5in Gsince D24 and D35 are disjoint. By Proposition 5.1, a 5-connected triangulation on Phas a split-K5Hwhose boundary coincides with the link of a specified vertex. Let [a, b] denote the path in Hjoining two vertices aand bwhich is contained in the path joining two nodes in H,where1≤i<j≤5. Moreover, we denote (a, b)=[a, b]−{a, b}, and also use the notations [a, b)and(a, b] similarly. The following claims that a boundary pair of nodes can be “moved” in a sense. Lemma 5.2. Suppose that a triangulation Gon Phas a split-K5Hwith boundary C.Let{a,a }be a boundary pair of nodes of H,andletQbe the plane subgraph of Gcorresponding to a face of Hwith nodes a,a ,b,c. Then, for some vertex aof [a,a ]in G, we can find a split-K5Hwith boundary Csuch that ais a node of H contained in neither a boundary pair nor an inner pair. Moreover, if bis contained in a boundary pair, then the number of the boundary pairs can be decreased in H; otherwise, bmight be contained in a new boundary pair of H. Proof. We may suppose that a vertex yof (a,c]andavertexzof (a,a ]arenot adjacent in Q. (For otherwise, replacing [a,y)withzy, we can regard zas a new a.) Then, by Lemma 3.5, we can take an internal a−xpath Pfor some xon either (a,b]or(b, c). In the former case, let H=H−(a,x)∪P(or H=H−(a,b )∪P when xis in (b, b) for an inner pair {b, b}). See Figure 3. Then we can decrease the number of boundary split pairs. In the latter case, let H=H−(a,b)∪P(or H=K−(a,b )∪Pwhen {b, b}is an inner pair), in which xmight be a new boundary pair. bc a bc a x x z y a a Fig. 3.Eliminate or move a boundary split node. Now we shall prove Lemma 2.1. Proof of Lemma 2.1. Let Gbe a 5-connected triangulation on P,andletuvw be any face of G. By Proposition 5.1, Ghas a split-K5Hwhose boundary ∂H coincides with the link of uin G.Letv1,v 2,v 3,v 4,v 5be five nodes of H(where  ∂H is fixed along the ordering of v1,...,v 5); some vi’s might be contained in boundary or inner pairs {vi,v i}of nodes. We shall deform Hto satisfy conditions (ii) and (iii) in the lemma. We may Downloaded 01/22/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php