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