Geometric Realization of Möbius Triangulations

Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. SIAM J. DISCRETE MATH.c 2008 Socie y o Indus ial and Applied Ma hema ics 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† Abs ac . AM¨obius iangula ion is a iangula ion on he M¨obius band. A geome ic ealiza ion o a map Mon a su ace Σ is an embedding o Σ in o a Euclidean 3-space R3such ha each ace o Mis a fla polygon. In his pape , we shall p o e ha e e y 5-connec ed iangula ion on he M¨obius band has a geome ic ealiza ion. In o de o p o e i , we p o e ha i Gis a 5-connec ed iangula ion on he p ojec i e plane, hen o any ace o G, heM¨obius iangula ion G− ob ained om Gby emo ing he in e io o has a geome ic ealiza ion. Key wo ds. geome ic ealiza ion, iangula ion, M¨obius band, p ojec i e plane AMS subjec classi ica ions. 05C10, 52B70, 05C83 DOI. 10.1137/070693382 1. In oduc ion. Le Σ be a su ace wi h a mos one bounda y componen , and le Mbe a map on Σ. I Σ has a bounda y, we suppose ha some cycle o M coincides wi h he bounda y o Σ. Such a cycle o Mis called he bounda y o M and deno ed by ∂M.A e exo Mno on ∂M is called an inne e ex. A k-cycle means a cycle o leng h k.A iangula ion onΣisamaponΣsuch ha each aceis bounded by a 3-cycle. In pa icula , a M¨obius iangula ion is a iangula ion on he M¨obius band. Fo an inne e ex o a iangula ion, he link o is he bounda y walk o he 2-cell egion consis ing o all aces inciden o . Th oughou his pape , we suppose ha he g aph o a map is simple, i.e., wi h no mul iple edges and no loops. Fo a cycle o pa h Cin M,acho d o Cmeans an edge xy o Msuch ha x, y ∈V(C) bu xy /∈E(C). Hence Cis induced in Mi and only i Chas no cho d. Ageome ic ealiza ion o a map Mon a su ace Σ is an embedding o Σ in o a Euclidean 3-space R3such ha each ace o Mis a fla polygon. S eini z’s heo- em s a es ha a sphe ical map has a geome ic ealiza ion i and only i i s g aph is 3-connec ed [10]. Mo eo e , A chdeacon, Bonning on, and Ellis-Monanghan p o ed ha e e y o oidal iangula ion has a geome ic ealiza ion [1]. In gene al, G ¨unbaum conjec u ed ha e e y iangula ion on any o ien able closed su ace has a geome ic ealiza ion [7], bu Bokowski and Guedes de Oli ei a ecen ly showed ha a iangu- la ion by K12 on he o ien able closed su ace o genus 6 has no geome ic ealiza ion [2]. (Fo ela ed opics, see [5].) Le us conside a geome ic ealiza ion o a iangula ion on he p ojec i e plane. Le Pdeno e he p ojec i e plane h oughou his pape . Since he p ojec i e plane i sel is no embeddable in R3, no map on Phas a geome ic ealiza ion. Le Gbe a iangula ion on P,andle be a ace o G.Le G− deno e he M¨obius iangula ion ∗Recei ed by he edi o s May 31, 2007; accep ed o publica ion (in e ised o m) Augus 22, 2008; published elec onically Decembe 19, 2008. h p://www.siam.o g/jou nals/sidma/23-1/69338.h ml †Depa amen o de Ma ema ica Aplicada I, Uni e si e de Se illa, Escuela Uni e si a ia A qui- ec u a Tecnica, A da Reina Me cedes S/N, 41012 Se illa, Spain (mjcha [email protected], alma @cica.es, emsua [email protected]). ‡Depa men o Compu e Science, Uni e si y o Ljubljana, 1000 Ljubljana, Slo enia (gaspe . fi[email p o ec ed]-lj.si). §Depa men o Ma hema ics, Yokohama Na ional Uni e si y, Yokohama 240-8501, Japan (nakamo [email protected]). 221 Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 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 iangula ion wi h no geome ic ealiza ion. ob ained om Gby emo ing he in e io o . Since he punc u ed su ace ob ained om Pby emo ing a 2-cell, he M¨obius band, is embeddable in R3,G− migh ha e a geome ic ealiza ion. The ollowing is known. Theo em 1.1 (Bonning on and Nakamo o [3]). E e y iangula ion Gon he p ojec i e plane Phas a ace such ha he M¨obius iangula ion G− has a geome ic ealiza ion. B ehm [4] has al eady ound a M¨obius iangula ion wi h no geome ic ealiza ion, shown in Figu e 1, in which bo h exp ess he same iangula ion. (In Figu e 1, we iden i y he e ices wi h he same label. In he igh -hand side, he shaded pa means he hole.) Why does B ehm’s example ha e no geome ic ealiza ion? We can p o e ha o each o i s spa ial embedding, he wo disjoin 3-cycles 123 and 456 ha e a linking numbe o a leas 2. (See [9] o he defini ion o he linking numbe .) Howe e , wo 3-cycles, each wi h an edge s aigh segmen embedded in R3,ha ea linking numbe o a mos 1, a con adic ion. Hence, gene alizing his example, we can see ha i a iangula ion Mon he M¨obius band has a bounda y cycle Co leng h 3anda3-cycleCdisjoin om Cwhich o ms an annula egion wi h C, henM ne e has a geome ic ealiza ion. Ag aphMis said o be cyclically k-connec ed i Mhas no sepa a ing se S⊂ V(M)wi h|S|≤k−1 such ha each connec ed componen o M−Shas a cycle. Then he cyclical 4-connec i i y o a iangula ion Gon Pis necessa y o a geome ic ealiza ion o G− o any ace o G. We conjec u e as ollows ha i is also sufficien . Conjec u e 1.2. Le Gbe a iangula ion on he p ojec i e plane P.Then G− has a geome ic ealiza ion o any ace o Gi and only i Gis cyclically 4-connec ed. In his pape , we p o e he ollowing. Theo em 1.3. Le Gbe a 5-connec ed iangula ion on he p ojec i e plane P. Then G− has a geome ic ealiza ion o any ace o G. By Theo em 1.3, a M¨obius iangula ion Mhas a geome ic ealiza ion i Mis ob ained om a 5-connec ed iangula ion Gon Pby emo ing a 2-cell. Le Mbe a 5-connec ed M¨obius iangula ion wi h a bounda y cycle C= 1··· k o leng h k.Le Pbe he map on Pob ained om Mbypas inga2-cell oC.I k=3, hen Pis a 5-connec ed iangula ion on P.I k=4, henPcanbeex ended oa5- connec ed iangula ion on Pby adding an edge 1 3o 2 4. (I his is impossible, hen Mwould ha e edges 1 3and 2 4, and hence Mwould con ain a quad angula ion Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 223 isomo phic o K4, con a y o he 5-connec i i y o M.) I k≥5, hen Pcan be ex ended o a 5-connec ed iangula ion on Pby adding a new e ex joined o all e ices on C. Hence we ha e he ollowing. Co olla y 1.4. E e y 5-connec ed M¨obius iangula ion has a geome ic eal- iza ion. Le Mbe a map on a su ace Σ wi h a bounda y, and le Cbe he bounda y cycle o M.Wesay ha Mis in e nally k-connec ed i Mis (k−1)-connec ed and i o any e ex ∈V(M−C), he e a e a leas kdisjoin pa hs om o C. Clea ly, i Gis a 5-connec ed iangula ion on P, hen o any ∈V(P), G− can be ega ded as an in e nally 5-connec ed M¨obius iangula ion whose bounda y cycle has a leng h o a leas 5. Hence we can elax he condi ion o Co olla y 1.4 o p o e he ollowing. Co olla y 1.5. E e y in e nally 5-connec ed M¨obius iangula ion has a geo- me ic ealiza ion i he bounda y cycle has a leng h o a leas 5. 2. Spli -K5’s in 5-connec ed iangula ions. Pu a 5-cycle C= 1 2 3 4 5 on P, called he bounda y,so ha Cbounds a 2-cell Ron P,whe eeach iis called anode. (We always fix i s o ien a ion  Calong he numbe ing o he e ices.) Join i o i+2 and i+3 by edges no in R o each i. Then he esul ing g aph is isomo phic o K5in which each ace excep Ris iangula . (See he le -hand side o Figu e 2.) Conside a spli ing (i.e., he in e se ope a ion o an edge con ac ion) o iin o wo adjacen e ices, iand  i, o deg ee 3. The e a e wo possibili ies o he spli ing. When iand  ilie on C(we always suppose ha iand  iappea on  Cin his o de ), { i,  i}is called a bounda y pai o nodes, and each o iand  iis called a bounda y spli node.(Thepa h om i o  ion  Cis called he bounda y spli in e al o { i,  i}.) O he wise, { i,  i}is called an inne pai o nodes, and each o iand  i is called an inne spli node, whe e we always suppose ha ilies on C.Le Kbe a map on Pob ained om he abo e K5by spli ings o some o i’s. A spli -K5is a subdi ision o Kon P. (See he igh -hand side o Figu e 2.) 0 1 2 3 3 4 0 0 1 2 3 3 4 0 K5Spli -K5  1  2  3  3 Inne pai Bounda y pai Fig. 2.K5and spli -K5. The ollowing is he mos impo an claim in his pape . I gua an ees ha a 5-connec ed iangula ion on Phas a special ype o a spli -K5. Lemma 2.1. Le Gbe a 5-connec ed iangula ion on P,andle u w be any ace o G.ThenGhas a spli -K5Hsuch ha (i) he bounda y ∂H o Hcoincides wi h he link o uin G. (ii) Hhas a mos one bounda y pai o nodes. (iii) i Hhas a bounda y pai , hen a leas one o and wis a bounda y spli node, bu he edge w is no con ained in a bounda y spli in e al. O he wise, o wis a node o H. Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 224 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ In he ollowing wo sec ions, we gi e p elimina ies o he p oo o Lemma 2.1. In sec ion 5, we p o e Lemma 2.1. 3. Lemmas. Le Gbe a g aph on P,andle Cbe a con ac ible cycle o G, i.e., one bounding a 2-cell on P. (A cycle o a closed cu e on a su ace is essen ial i i is no con ac ible.) Then Ccu s Pin o wo su aces, one homeomo phic o an open disk and he o he homeomo phic o an open M¨obius band. Le in C(G)deno e he g aph consis ing o he e ices and edges lying in he disk componen o C,andle In C(G) be he g aph consis ing o he e ices and edges lying on Cand in he disk componen o C. We define ex C(G)andEx C(G) analogously. No e ha In C(G)is no necessa ily an induced subg aph o G. Le C= 1 2 3 4··· kbe a cycle. A closed segmen [ i, j]isa i− jpa h along  C.Anopen segmen ( i, j) is ob ained by dele ing he end e ices o he co esponding closed segmen . Mo eo e , we use he no a ions [ i, j)and( i, j], defined simila ly. Lemma 3.1. Le Gbe a 5-connec ed iangula ion on P.Le C= 1 2 3 4be a con ac ible 4-cycle in G.Thenin C(G)con ains no e ices. P oo . Assume ∈V(in C(G)). Since Gis 5-connec ed, ex C(G)con ainsno e ices. Then we can add only wo edges 1 3and 2 4ou side C,sinceTis simple. Hence his con adic s ha Gis a iangula ion. Lemma 3.2. Le be a e ex o a 5-connec ed iangula ion Gon P,andle Cbe a con ac ible 5-cycle con aining in i s in e io . Then he e exis s a unique con ac ible 5-cycle Cso ha In C(G)con ains all con ac ible 5-cycles which con ain in hei espec i e in e io s. P oo .Le C1and C2be con ac ible 5-cycles con aining in hei in e io s, and suppose ha In C1(G)andIn C2(G)a einclusionwise incompa able, ha is, nei he In C1(G)⊆In C2(G)no In C1(G)⊇In C2(G). I suffices o p o e ha he e is a con ac ible 5-cycle Csuch ha In C(G) con ains bo h In C1(G)andIn C2(G). Since C1and C2a e o leng h 5 and nei he one is con ained in he closed in e io o he o he , hey in e sec in exac ly wo e ices. These wo e ices di ide Ciin o a segmen lying in he in e io o C3−iand one lying in he ex e io o C3−i,whe ei= 1,2. Combining he common segmen s and bo h in e io segmen s yields a con ac ible cycle, which con ains in i s in e io . By Lemma 3.1, i s leng h is a leas 5. Combining he wo ex e io segmen s wi h he wo common segmen s, we ob ain a con ac ible cycle Co leng h a mos 5, since bo h C1and C2we e 5-cycles. Since Gis simple, Ccon ains no essen ial cycle, and hence i is a con ac ible cycle in G.NowChas leng h 5 by Lemma 3.1 since i con ains in i s in e io . On he o he hand, In C(G) con ains bo h In C1(G)andIn C2(G), and he p oo is comple e. Lemma 3.3. Le Gbe a 5-connec ed iangula ion on P,andle C= 1 2 3 4 5 be a con ac ible 5-cycle in G.I Ghas no e ex in he ex e io o C, henEx C(G) is isomo phic o K5. P oo . We ha e o show ha ex C(G) con ains e e y possible edge i i+2 (in in- dices modulo 5). A simila a gumen as in he p oo o Lemma 3.1 does he ick. The ollowing lemma is an immedia e consequence o 5-connec i i y. Lemma 3.4. Le Gbe a 5-connec ed iangula ion on P,andle ∈V(G).Le and  be wo nonconsecu i e neighbo s o .I and  ha e ano he common neighbo wwhich is no adjacen o , hen he cycle w  is essen ial. Le Dbe a plane g aph wi h bounda y cycle Cand each inne ace iangula , and le x, y be dis inc e ices o C.Anin e nal x−ypa h is a pa h in Djoining x and yand in e sec ing Conly a i s end e ices. Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 225 Lemma 3.5. Le Dbe a iangula ion on he disk wi h bounda y cycle C,andle x, y be dis inc e ices o Cwi h xy /∈E(C).ThenDhas an in e nal x−ypa h i and only i Dhas no cho d pq o some p, q ∈V(D)−{x, y}such ha xand ya e con ained in dis inc componen s o C−{p, q}. P oo . The sufficiency is ob ious and so we conside he necessi y. Suppose ha C has a cho d pq. By he assump ion, xand ya e con ained in one, say D1,o he wo subg aphs D1,D 2such ha V(D)=V(D1)∪V(D2)andV(D1)∩V(D2)={p, q}. In his case, we ha e o look o a equi ed in e nal x−ypa h in D1. Hence in he ollowing a gumen , we may suppose ha Dhas no cho d. Obse e ha since Cis cho dless, each e ex on Cis adjacen o a leas one e ex in D−C.Mo eo e , we can see ha in C(D) is connec ed. (Fo o he wise, i.e., i in C(D) is disconnec ed, hen he e a e wo e ices p,q∈Csuch ha D−{p,q}is disconnec ed. Howe e , his is impossible since each inne ace o Dis iangula .) Hence we ha e an in e nal x−ypa h in D. Le Cbe a con ac ible cycle o leng h a leas 4 in a iangula ion G. Suppose ha e ices 1, 2, 3, 4lie along Cin his o de , bu hey do no need o be consecu i e along C. Le us also assume ha he segmen s [ 1, 2], [ 2, 3], [ 3, 4], and [ 4, 1] ha e no cho ds in In C(G). We say ha In C(G)isa4-pa ch wi h nodes 1, 2, 3, 4. We ob ain he ollowing h ee lemmas, ca e ully applying Lemma 3.5 o P. Lemma 3.6. Le Pbe a 4-pa ch wi h nodes 1, 2, 3, 4. Assume ha 1 4, 2 3∈ E(P)and ha uand a e e ices om ( 1, 2)and ( 3, 4), espec i ely. Then P− { 1, 2, 3, 4}con ains an u− pa h, o a pai o an ipodal nodes a e adjacen . Lemma 3.7. Le Pbe a 4-pa ch wi h nodes 1, 2, 3, 4.ThenP−{ 1, 3}con ains an 2− 4pa h unless 1 3∈E(P). Le Pbe a 4-pa ch wi h nodes 1, 2, 3, 4.An 2− 4diagonal in Pis an 2− 4 pa h Q=u1u2u3···uk−1uk(u1= 2and uk= 4)inP−{ 1, 3}i he e exis s indices i<jsuch ha (D1) he ini ial segmen u1···uiis a segmen o ∂P, (D2) he e minal segmen uj···ukis a segmen o ∂P,and (D3) he in e media e segmen ui···ujis a segmen o Psuch ha ui,u j∈V(∂P) and ha all o he e ices lie in in (P). I Qis an 2− 4diagonal in P, heni isalsoan 4− 2diagonal. Fu he , i a pa ch Pwi h nodes 1, 2, 3, 4con ains an 2− 4pa h a oiding 1and 3, heni also con ains an 2− 4diagonal. We say ha an 2− 4diagonal Qlies closes o 1i he numbe o aces o P bounded by Qand he segmen s inciden wi h 1is as small as possible. Lemma 3.8. Le Pbe a 4-pa ch wi h nodes 1, 2, 3, 4,andle Qbe he 2− 4 diagonal closes o 1.Le uiand ujbe he i s and las e ex o he in e media e segmen o Q, espec i ely. Then 1is adjacen o ui,u i+1,...,u j−1,u jin P. 4. Essen ial 3-linkages. Anea iangula ion Ris a map on Pwi h a dis in- guished ace such ha e e y o he ace o Ris iangula , and ha he acial walk along is a cycle. Suppose ha he bounda y cycle o , deno ed by W, has a leng h o a leas 6. Le 1, 2, 3, 4, 5, 6be six e ices ha appea along Win his o de bu ha do no need o be consecu i e along W.Anessen ial 3-linkage (wi h espec o 1, 2, 3, 4, 5, 6) is a collec ion Lo h ee disjoin pa hs P1,P2,P3so ha Piis a i− i+3 pa h o i=1,2,3. I is easy o see ha W∪Picon ains some essen ial cycle. Le Q1be some minimal subpa h o P1so ha W∪Q1s ill con ains an essen ial cycle. Also Q1,P 2,P 3 o m an essen ial 3-linkage wi h possibly diffe en end e ices. By applying he same idea on P2and P3, we ob ain he ollowing lemma. Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 226 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ Lemma 4.1. Le Lbe an essen ial 3-linkage wi h espec o nodes 1,..., 6. The e exis s an essen ial 3-linkage Lso ha e e y pa h in Lin e sec s Wonly a i s end e ices. The second esul has been, in g ea e gene ali y, p o ed by Robe son and Sey- mou in [8]. We s a e i adap ed o ou needs. Theo em 4.2 (Robe son and Seymou [8]). Le Rbe a nea iangula ion o P and = 1 2 3 4 5 6i s dis inguished ace o leng h 6.ThenRcon ains an essen ial 3-linkage wi h espec o 1, 2, 3, 4, 5, 6i and only i (L1) Rcon ains no pai o pa allel nonhomo opic edges wi h common end e ices; (L2) Rdoes no con ain a con ac ible cycle Co leng h a mos 5whose in e io con ains . A pai o pa allel nonhomo opic edges iola ing (L1) o ms an essen ial cycle o leng h 2. T a e sing hese wo edges wice yields a con ac ible (bu no simple) closed walk whose “in e io ” con ains all aces o R. This obse a ion enables bo h condi ions (L1) and (L2) o be combined in o a single condi ion, albei wi h sligh adap a ions. Fo p ac icali y, we p e e he condi ions o be w i en sepa a ely, since hey a e o diffe en fla o s and ha e o be ackled wi h diffe en app oaches. We look o essen ial 3-linkages in nea iangula ions. In he case when he leng h o he dis inguished ace exceeds 6, we fi s decide which six e ices a e he end e ices o a linkage. The es o his sec ion is de o ed o he p oo o he ollowing. P oposi ion 4.3. Le Gbe a 5-connec ed iangula ion o P,andle be a e ex o deg ee d≥6.Le D=u1u2···udbe he link o in G. Then he nea iangula ion R=G− con ains an essen ial 3-linkage i and only i is no con ained in he in e io o a con ac ible cycle o leng h a mos 5. P oo . Clea ly a cycle con aining in i s in e io mee s each pa h in an essen ial 3- linkage a leas wice. The difficul y lies in he o he di ec ion—how o find a linkage— i is no con ained in he in e io o a “sho ” con ac ible cycle. An edge e∈E(R)issaid obeessen ial i he end e ices o elie in Dand D∪e con ains an essen ial cycle. We shall spli he p oo o P oposi ion 4.3 wi h espec o he numbe o essen ial edges. I Rcon ains a se o h ee independen essen ial edges, hen no u he p oo is needed. This lea es us wi h he case whe e a maximal se o independen essen ial edges con ains a mos wo edges. Assume nex ha Rcon ains a se o wo independen essen ial edges. The ou end e ices o hese essen ial edges spli he - acial walk in o ou open segmen s. Le us choose essen ial edges e= 1 4and e= 3 6in such a way ha he union o wo consecu i e open segmen s ( 1, 6)∪( 3, 4)inDcon ains as ew e ices as possible. Suppose ha ( 1, 3)con ainsa e ex,say 2,and ha ( 4, 6)con ainsa e ex, say 5.Nowi 1 6∈E(R)−E(D), hen he con ac ible cycle 4 1 6sepa a es 2 om 5,andi 3 4∈E(R)−E(D), hen he con ac ible cycle 3 4 1sepa a es 2 om 5. Nei he can happen since Gis 5-connec ed. By Lemma 3.6, we can join 2and 5by a pa h a oiding 1, 2, 3,and 4, and hence we can find an essen ial 3-linkage. So we assume ha he e exis s a se o wo independen essen ial edges e=w1w3 and e=w2w4so ha w1,w 2,andw3lie consecu i ely along D. We may also assume ha w4lies close o w3 han o w1along D, and ha no essen ial edge inciden wi h w2has he o he end e ex in (w3,w 4). Deno e he e ices along Dby 1, 2, 3,..., d so ha 1=w1and 2=w2(also 3=w3, bu hen his may no go on). Add o R he new edges 1 k,whe ek=6,...,d−1, and deno e he esul ing nea iangula ion wi h R, wi h he dis inguished ace o size 6. Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 227 I is easy o see ha Rsa isfies (L1), since he newly added edges do no ha e hei essen ial coun e pa s. Simila ly, a sho con ac ible cycle Ccon aining he dis inguished ace o Rin i s in e io , i.e., con adic ing (L2), would ha e o use some new edge 1 k,whe ek≥6. Now Cwould con ain e ices k,w 1,w 2,andw3, which implies ha e ices kand w3ha eacommonneighbo inR. This con adic s Lemma 3.4 since Cis con ac ible. Hence Rcon ains an essen ial 3-linkage. Since all new edges sha e a common end e ex, we can, i necessa y, ans o m he linkage in o an essen ial 3-linkage in R. Suppose nex ha he e is an essen ial edge bu we canno find a se o wo independen essen ial edges. Le e=w1w2be he essen ial edge, and assume ha he segmen (w1,w 2) is as sho as possible. Since Gis simple, w1and w2a e no consecu i e along D. Deno e he e ices o Dso ha w1= 3and 4lies in (w1,w 2). As (w1,w 2) is as sho as possible, we ha e w2= 1. As in he p e ious case, le Rbe he nea iangula ion ob ained by adding new edges 1 k,whe ek=6,...,d−1. We will a gue ha Rhas an essen ial 3-linkage. I Rdoes no sa is y (L1), hen an essen ial edge emus be inciden wi h bo h 1and k o some ksa is ying 6 ≤k≤d. By in e lacing essen ial edges inciden o k∈[w1,w 2]=[ 3,w 2], we clea ly ha e k= 3. On he o he hand, kcanno lie in (w1,w 2)=( 3,w 2), as wo independen essen ial edges canno exis , and hence k=w2. Bu his con adic s 5-connec i i y o G, since he 4-cycle 1 k 3= 1w2w1 sepa a es 2and 4. Nex assume ha Rcon adic s (L2). The sho cycle Ccon adic ing (L2) can be di ided in o h ee segmen s: he fi s one be ween 1and w1, he second be ween w1and w2, and he hi d be ween w2and 1. Thei leng hs a e a leas 2, 2, and 1, espec i ely, using he ac ha nei he 1and w1= 3no w1and w2a e consecu i e along D, and he ac ha Cuses one o he new edges. Since he leng h o Cis a mos 5, all lowe bounds a e sha p. By Lemma 3.4, Cmus pass h ough 2,andalso Cmus pass h ough 4and w2= 5. On he segmen be ween w2and 1 he cycle C uses exac ly one edge, namely 1w2= 1 5, and i also has o use one new edge. This is a con adic ion, so Rsa isfies bo h (L1) and (L2), and Rcon ains an essen ial 3-linkage. As in he p e ious case we can, i necessa y, ans o m he linkage in o an essen ial 3-linkage in R. We a e le wi h he case whe e Rcon ains no essen ial edges. E en i we add new edges o he in e io o , we canno con adic (L1), and ou only conce n will be mee ing he condi ion (L2). We p oceed nai ely. Le us assign labels 1, 2,..., d o neighbo s o in he o de o hei indices. Add new edges o he o m 1 k,whe ek=6,...,d−1. The newly ob ained nea iangula ion Rmay con ain an essen ial 3-linkage, and we win. On he o he hand, i may no , as we con adic (L2), and we lose.In hiscase,R con ains a sho cycle Cwhich uses a new edge 1  o some ∈{6,...,d−1}. Hence we assume ha we lose o e e y assignmen o labels 1, 2,..., d o he consecu i e neighbo s o . Now fix an assignmen o labels so ha he e exis s a cycle C con adic ing (L2) using a new edge 1 k,whe ekis as la ge as possible. Le us deno e w1= 1,w2= 2,w3= 3,w4= k−1,w5= k,andw6= k+1. Fu he , le us add new edges joining w1 o e ices o (w6,w 1) and addi ional new edges joining w3 o e ices o (w3,w 4). We deno e he newly ob ained nea iangula ion by Rw. We claim ha Rwcon ains an essen ial 3-linkage. Assume ha his is no he case, and le Cwbe he obs uc ion acco ding o (L2). Clea ly Cwcon ains a leas one new edge. Obse e ha Cwcanno con ain bo h a Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 228 CH´ AVEZ, FIJAVˇ Z, M´ ARQUEZ, NAKAMOTO, AND SU´ AREZ new edge inciden wi h w1and a new edge inciden wi h w3, since a segmen o Cwo leng h a mos 2 would join wo nonconsecu i e e ices o D. The cycle Cwcanno con ain a new edge inciden wi h w1since his would con adic maximali y o k. Hence, Cwcon ains a new edge inciden wi h w3.Nowle Cbe he cycle con aining he edges o Cwlying ou side C and he edges o C lying ou side o Cw.ThenCis a con ac ible cycle con aining in i s in e io . Le P⊆Cw∪C be he 1− 3pa h whose edges lie in he in e io o C. Since i connec s wo nonconsecu i e e ices along , i s leng h is a leas 3. This implies ha he leng h o Cis a mos 5, a con adic ion. Hence Rwcon ains an essen ial 3-linkage, and consequen ly Ralso con ains an essen ial 3-linkage. This comple es he p oo o P oposi ion 4.3. 5. P oo o Lemma 2.1. In his sec ion, we shall p o e Lemma 2.1. We begin wi h he ollowing p oposi ion. P oposi ion 5.1. Le Gbe a 5-connec ed iangula ion on P,andle u∈V(G). Then Ghas a spli -K5Hwhose bounda y coincides wi h he link o uin G. P oo . We will spli he analysis in o wo cases ega ding he p ope ies o uand ea one o he wo cases by e e ing o [6]. Le Dbe he link o u. Case 1. Gcon ains a con ac ible 5-cycle C= 1 2 3 4 5such ha u∈V(in C(G)). By Lemma 3.2, we may assume ha Cis he maximal 5-cycle con aining uin i s in e io . Since Gis 5-connec ed, he e exis in e nally disjoin u− ipa hs Pi o i=1,...,5. In o de o find a sui able spli -K5, we need o find a subg aph o Ex C(G) which con ac s o he zigzag cycle 1 3 5 2 4. This ask has been ea ed in g ea e gene ali y in [6, subsec ion: Finding a sui able cycle mino Uin Gx]. Hence we can ob ain a spli -K5Hwhose bounda y is C.Nowle H=(H−E(C)) ∪D∪ 5  i=1 (Pi−{ }). Then His a spli -K5wi h bounda y D, in which he e is no bounda y pai . Case 2. udoes no lie in he in e io o a con ac ible 5-cycle. Then we clea ly ha e |D|=deg(u)=k≥6. Le be he dis inguished ace o G− wi h bounda y D. By Theo em 4.2, G− con ains an essen ial 3-linkage L={P1,P 2,P 3}wi h espec o u1,u 2,u 3,u 4,u 5,u 6,whe ePijoins uiand ui+3 o i=1,2,3. We may also assume ha each Piin Lhas no cho d. Then Ldi ides he nea iangula ion G− in o h ee pa ches R12,R23,andR13, whose nodes a e (u1,u 2,u 5,u 4), (u2,u 3,u 6,u 5), and (u3,u 4,u 1,u 6) lying on hei bounda y in his o de , espec i ely. We fi s claim ha hese pa ches con ain wo e ex-disjoin diagonals. Le us fi s p o e ha e e y wo pa ches, say R12 and R23, con ain diagonals wi h disjoin end e ices. Suppose his is no he case, and le , say, u2be an end e ex o e e y possible diagonal in bo h R12 and R23. By Lemma 3.7, we ha e u2u4∈E(R12)and u2u6∈E(R23).This con adic s he 5-connec i i y o Gsince {u, u2,u 4,u 6}sepa a es 5and 1in G. Hence we may assume ha R12 con ains a u1−u5diagonal D15 and ha R23 con ains a u2−u6diagonal D26. We fi s suppose ha D15 and D26 a e disjoin . In his case, we can ob ain a equi ed spli -K5Hsuch ha H=D∪L∪D15 ∪D26. Now conside he case when D15 and D26 sha e an inne e ex. Le us y o push he diagonals away: suppose ha D15 and D26 a e closes o u4and u3, espec i ely. I D15 and D26 a e no e ex disjoin , hen he e minal segmen So D15 in e sec s Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. GEOMETRIC REALIZATION OF M ¨ OBIUS TRIANGULATIONS 229 he ini ial segmen So D26 a P2.Le wbe he fi s e ex o S,andle wbe he las e ex o S. Then, by Lemma 3.8, we ha e bo h u4w∈E(R12)andu3w∈E(R23). I w=w, hen we can find a u2−u4diagonal in R12 h ough wu4and a u3−u5 diagonal in R23 h ough u3w. Since hey a e disjoin , we a e done, simila ly as abo e. Suppose ha w=w.Sinceu4w∈E(R12), we ocus on he 4-pa ch R 12 wi h nodes u1,u 2,w,u 4con ained in R12.No e ha u1w/∈E(R 12). (Fo o he wise, {u, u1,w,u 3}sepa a es u2and u4,sinceu3w∈E(R23). This con adic s he 5- connec i i y o G.) Hence R 12 admi s a u2−u4diagonal D24, a oiding wand u1,by Lemma 3.7. Le D35 be he u3−u5diagonal o R23 h ough u3w.ThenD∪L∪D24∪D35 is a equi ed spli -K5in Gsince D24 and D35 a e disjoin . By P oposi ion 5.1, a 5-connec ed iangula ion on Phas a spli -K5Hwhose bounda y coincides wi h he link o a specified e ex. Le [a, b] deno e he pa h in Hjoining wo e ices aand bwhich is con ained in he pa h joining wo nodes in H,whe e1≤i<j≤5. Mo eo e , we deno e (a, b)=[a, b]−{a, b}, and also use he no a ions [a, b)and(a, b] simila ly. The ollowing claims ha a bounda y pai o nodes can be “mo ed” in a sense. Lemma 5.2. Suppose ha a iangula ion Gon Phas a spli -K5Hwi h bounda y C.Le {a,a }be a bounda y pai o nodes o H,andle Qbe he plane subg aph o Gco esponding o a ace o Hwi h nodes a,a ,b,c. Then, o some e ex ao [a,a ]in G, we can ind a spli -K5Hwi h bounda y Csuch ha ais a node o H con ained in nei he a bounda y pai no an inne pai . Mo eo e , i bis con ained in a bounda y pai , hen he numbe o he bounda y pai s can be dec eased in H; o he wise, bmigh be con ained in a new bounda y pai o H. P oo . We may suppose ha a e ex yo (a,c]anda e exzo (a,a ]a eno adjacen in Q. (Fo o he wise, eplacing [a,y)wi hzy, we can ega d zas a new a.) Then, by Lemma 3.5, we can ake an in e nal a−xpa h P o some xon ei he (a,b]o (b, c). In he o me case, le H=H−(a,x)∪P(o H=H−(a,b )∪P when xis in (b, b) o an inne pai {b, b}). See Figu e 3. Then we can dec ease he numbe o bounda y spli pai s. In he la e case, le H=H−(a,b)∪P(o H=K−(a,b )∪Pwhen {b, b}is an inne pai ), in which xmigh be a new bounda y pai . bc a bc a x x z y a a Fig. 3.Elimina e o mo e a bounda y spli node. Now we shall p o e Lemma 2.1. P oo o Lemma 2.1. Le Gbe a 5-connec ed iangula ion on P,andle u w be any ace o G. By P oposi ion 5.1, Ghas a spli -K5Hwhose bounda y ∂H coincides wi h he link o uin G.Le 1, 2, 3, 4, 5be fi e nodes o H(whe e  ∂H is fixed along he o de ing o 1,..., 5); some i’s migh be con ained in bounda y o inne pai s { i,  i}o nodes. We shall de o m H o sa is y condi ions (ii) and (iii) in he lemma. We may Downloaded 01/22/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php