On 4-connected geometric graphs

XV Spanish Mee ing on Compu a ional Geome y, June 26-28, 2013 On 4-connec ed geome ic g aphs Al edo Ga cía ∗ 1 , Clemens Hueme † 2 , Ja ie Tejel ‡ 1 , and Pa el Val § 3 1 Dep . Mé odos Es adís icos. Uni e sidad de Za agoza. Spain. 2 Dep . Ma emà ica Aplicada IV. Uni e si a Poli ècnica Ca alunya, Spain. 3 Depa men o Applied Ma hema ics. Cha les Uni e si y, Czech Republic. Abs ac Gi en a se S o n poin s in he plane, in his pape we gi e a necessa y and some imes sucien condi ion o build a 4-connec ed non-c ossing geome ic g aph on S . In oduc ion Gi en a se S o n poin s in he plane, a non-c ossing geome ic g aph on S is a g aph in which i s e ices a e he poin s o S and i s edges a e s aigh -line seg- men s be ween hese poin s such ha no edge passes h ough a e ex die en om i s endpoin s and any wo edges may in e sec only a a common endpoin . Since all he geome ic g aphs conside ed in his pape a e non-c ossing, h oughou he pape we will use he e m geome ic g aph, meaning ha he geo- me ic g aph is non-c ossing. The s udy o geome ic g aphs and, in pa icula , he s udy o p oblems on how o embed plana g aphs as geome ic g aphs on gi en poin se s is a e y ac i e a ea o esea ch ( o a e iew on geome ic g aphs and some ela ed opics, see o example [1, 4]). One o hese p oblems is he p oblem o building geome ic g aphs wi h a ce ain connec i i y on a se o poin s S .We will say ha a se o poin s S is k -connec ible i i admi s a k -connec ed geome ic g aph on i . Fo k= 1,2,3 , i is well-known when S is k -connec ible and how o build a k -connec ed geome ic g aph (see [2, 3]). Gi en S , i is enough o build a non-c ossing ee on S ( o example he minimum spanning ee o ∗ Email: ola [email p o ec ed]. Resea ch pa ially suppo ed by p ojec s Gob. A ag. E58-DGA, MINECO MTM2012-30951 and ESF EUROCORES p og amme Eu oGIGA, CRP Com- PoSe: MICINN P ojec EUI-EURC-2011-4306. † Email: clemens.hueme @upc.edu. Resea ch pa ially sup- po ed by p ojec s MINECO MTM2012-30951 and ESF EU- ROCORES p og amme Eu oGIGA, CRP ComPoSe: MICINN P ojec EUI-EURC-2011-4306. ‡ Email: [email p o ec ed]. Resea ch pa ially suppo ed by p ojec s Gob. A ag. E58-DGA, MINECO MTM2012-30951 and ESF EUROCORES p og amme Eu oGIGA, CRP Com- PoSe: MICINN P ojec EUI-EURC-2011-4306. § Email: al @kam.m.cuni.cz. S ) when k= 1 , and i is enough o build a simple polygoniza ion o S when k= 2 . Fo he case k= 3 , he only se o poin s no admi ing a 3-connec ed geome ic g aph is he con ex case. O he wise, in [3] he au ho s gi e an algo i hm o build a 3-connec ed geome ic g aph using max{d3n/2e, n+m−1} edges, whe e m is he numbe o poin s on he bounda y o he con ex hull o S , and hey p o e ha he e is no 3-connec ed plane g aph on S wi h less edges. Howe e , o k > 3 , li le is known abou when a se o poin s is k -connec ible. Fo k= 4 , Dey e al. [2] show poin s se s ha do no admi any 4-connec ed geome ic g aph on hem and hey p o ide a neces- sa y and sucien condi ion o poin se s whose con- ex hull consis s o exac ly h ee poin s. A gene al cha ac e iza ion o 4- o 5-connec ible se s o poin s is no known. In his pape , we s udy se s o poin s ha a e 4- connec ible. We dene a condi ion ( he U-condi ion) ha any se o poin s mus sa is y o be 4-connec ible and we show ha he U-condi ion is always sucien o some se s o poin s. By deno ing he con ex hull o S by CH(S) and he se o poin s on he bounda y o he con ex hull o S by H(S) , i Q=H(S) , I=S Q and P=H(I) , hen he U-condi ion is sucien o se s o poin s in which Q∪P sa ises he U-condi ion. 1 The U-condi ion In his sec ion, we will dene he U-condi ion and we will see ha i is a necessa y condi ion o ge 4- connec ed geome ic g aphs. A subse C o poin s o Q is connec ed i i consis s o consecu i e poin s o Q . We will deno e by h(C) he numbe o connec ed componen s o a subse C o Q . Deni ion 1 A se S o poin s sa ises he U- condi ion i i) |Q| ≤ |I| ii) Fo any se C⊂Q , |H(S C)| ≤ |I|+h(C) . Lemma 2 E e y 4-connec ible se S sa ises he U- condi ion. 123 On 4-connec ed geome ic g aphs P oo . Le us p o e ha i G(S) is a 4-connec ed g aph d awn on S , hen S has o sa is y i) and ii). In G(S) , each e ex mus ha e deg ee a leas 4, and since he e a e no edges linking non-consecu i e poin s o Q (o he wise G(S) would no be 3-connec ed), hen he e a e a leas 2|Q| edges ha ing an endpoin in Q and he o he one in I . On he o he hand, as G(S) is 4-connec ed, each poin o I can be linked o a maximum o wo (and consecu i e) poin s o Q . Hence, a mos he e a e 2|I| edges wi h an endpoin in Q and he o he one in I . The e o e, 2|Q| ≤ 2|I| and he necessi y o i) is p o ed. Now, suppose C6=∅ is a subse o poin s o Q and C1, C2, . . . , Ch(C) a e i s connec ed componen s. Le us deno e by Ci he poin s o Q placed be ween componen Ci and componen Ci+1 . Thus, Q consis s o he poin s C1, C1, C2, C2, . . . , Ch(C), Ch(C) in his o de . When we emo e he poin s o C , all he poin s in he subse s Ci emain in H(S C) and pe haps, be ween Ci and Ci+1 (mod h(C) ), a subse Ii+1 o poin s o I appea s in H(S C) . Ei he Ii is emp y o i consis s o consecu i e poin s o P (see Figu e 1). Le I be he se I (I1∪I2∪. . . ∪Ih(C)) and le C be he se Q C . Obse e ha p o ing ii) is equi alen o p o ing |C|≤|I|+h(C) . C2 C1 I2 I1q1 qk p1 C2 I3 I C3 C1 C3 Figu e 1: Illus a ion o Lemma 2. Suppose ha I1={p1, . . . , pk0} is nonemp y and le q1 and qk be he poin s o C placed on he bounda y o CH(S C) jus a e and be o e he poin s o I1 , espec i ely (see Figu e 1). Wi hou loss o gene ali y, we can assume ha G(S) is a iangula ion. So, each poin o I1 mus be connec ed in G(S) o some poin o C1 and, since G(S) is 4-connec ed, hey canno be connec ed o a poin o C , excep o he edges pk0q1 and qkp1 . The e o e, o an edge linking a poin o C wi h an in e io poin (a leas 2|C| edges), he in e io endpoin mus be in I I1 , excep o he wo men ioned edges pk0q1 and qkp1 . We can epea he same easoning o e e y subse Ii , ob aining ha he e mus be a leas 2|C| − 2h(C) edges wi h an endpoin in C and he o he one in I . On he o he hand, as be o e, he e a e a mos 2|I| connec ions o his ype, so i ollows ha 2|C| − 2h(C)≤2|I| .  Obse e ha i |Q|= 3 , hen |I|+1 = n−2 . Hence, pa ii) can only ail i we emo e one poin q o Q and he bounda y o CH(S q) con ains all he emaining poin s. In [2], his is he condi ion ha is p o ed o be necessa y and sucien o build a 4-connec ed geome ic g aph (in ac a iangula ion) on S . Las ly, le us poin ou ha , gi en S , checking whe he S sa ises he U-condi ion o no can be done in O(|Q|+|P|) s eps, a e calcula ing Q and P . The algo i hm is based in he obse a ion (no easy o p o e) ha i is no necessa y o compu e CH(S C) o all he possible subse s C , bu only o a linea numbe o hem. 2 Some 4-connec ible se s In his sec ion, we will gi e some se s o poin s o which he U-condi ion is sucien . In pa icula , we will see ha i Q∪P sa ises he U-condi ion o a se o poin s S , hen S is 4-connec ible. We will use Q ( P ) o e e o he con ex polygon dened by he poin s o Q ( P ). Le us s a wi h he case in which S is p ecisely Q∪P and |Q|=|P| . Lemma 3 Le Q={q1, . . . , qn} be a se o poin s in con ex posi ion and le P={p1, . . . , pn} be ano he se o poin s in con ex posi ion such ha P is inside Q . Suppose ha he se o poin s S=Q∪P sa ises he U-condi ion. Then S is 4-connec ible. P oo . Le M be he egion CH(Q) CH(P) . To p o e he lemma, i is enough o ob ain a c ossing ee zig-zag cycle Z=piqjpi+1qj+1 . . . pi−1qj−1pi such ha i s edges a e in M , because hen he edges o Z and he edges o Q and P dene a 4-connec ed g aph (see Figu e 2). P Q Z Figu e 2: A 4-connec ed geome ic g aph when S= Q∪P . We will say ha a iangle qjpipi+1 is legal i i is con ained in egion M . P o ing he lemma is equi alen o p o ing ha he e is a sequence o n 124 XV Spanish Mee ing on Compu a ional Geome y, June 26-28, 2013 consecu i e legal iangles qjpipi+1, qj+1pi+1pi+2,..., qj+n−1pi+n−1pi+n , whe e poin s wi h equal subsc ip s modulo n a e conside ed iden ical. Le us assume ha {q1, . . . , qm} is he se o clock- wise poin s o Q on he le o he line p1p2 . The ollowing algo i hm compu es a sequence o n consec- u i e legal iangles. Begin Do i=j= 2 While (i≤n) Do (* In a ian (1) : T iangles o he sequence qj−1pi−1pi, qj−2pi−2pi−1, . . . , qj−(i−1)p1p2 a e legal.*) I ( T iangle qjpipi+1 is legal ) hen Do {i=i+ 1; j=j+ 1} Else (* In a ian (2) : qj is be ween qj−1 and he  s c ossing o line pipi+1 wi h Q *) Do j=j+ 1 End o While (* A e nishing he algo i hm, all he iangles o he sequence qj−np1p2, qj−(n−1)p2p3, . . . , qj−1pnp1 a e legal.*) Le us see ha asse ions (1) and (2) a e always ue, so hey a e in a ian in he algo i hm. T i ially, asse ion (1) is ue he  s ime because q1p1p2 is legal by hypo hesis. Now, suppose ha as- se ions (1) and (2) a e ue in he i e a ions 1,2, . . . , k o he loop and le us p o e ha (1) is s ill ue in he ollowing i e a ion. I we begin he k+ 1 i e a ion a - e explo ing a legal iangle in he i e a ion k , hen clea ly (1) is s ill ue (because we a e adding he las explo ed iangle o a p e ious legal sequence). I we begin i e a ion k+1 a e explo ing an illegal iangle qjpipi+1 in i e a ion k , hen we need o check ha he new sequence ST =qjpi−1pi, . . . , qj−i+2p1p2 o iangles (whe e j has been inc eased by one) is legal. Assume o he con a y ha in his sequence ST a  s illegal iangle qj−hpi−h−1pi−h appea s, so qj−h is he  s clockwise poin o Q on he igh o line pi−h−1pi−h . By emo ing he poin s o Q om qj+1 o qj−h−1 (see Figu e 3 le ), hen he poin s o P om pi o pi−h ( n−h+1 poin s) and he poin s o Q om qj−h o qj ( h+1 poin s) appea in he bounda y o he new con ex hull, con adic ing he U-condi ion (a mos n+ 1 poin s can appea in he bounda y o he new con ex hull). The e o e (1) is in a ian . Fo asse ion (2), he  s ime ha he algo- i hm goes o he else b anch, we a e explo ing he illegal iangle qjpjpj+1 , being he iangles qj−1pj−1pj, . . . , q1p1p2 legal. I qj was on he igh side o pipi+1 and a e he second c ossing poin o ha line wi h Q , hen, by emo ing he poin s o Q om q1 o qj−1 ( emembe ha q1 is he  s poin o Q o he le o p1p2 ), he U-condi ion is con adic ed because in he bounda y o he new con ex hull n+ 2 P Qpi pi+1 pi−1 qj qj−hpi−h+1 pi−h pi pi+1 qj qj−1 qj1 pi1 pi1+1 pi1−1 Q1 P pi−h−1 Q1 Q Figu e 3: Illus a ion o Lemma 3. Le : Supposing qj−h is on he igh o pi−h−1pi−h , he U-condi ion ails i Q1 is emo ed. Righ : Supposing qj is on he igh o pipi+1 , he U-condi ion ails i Q1 is emo ed. poin s appea ( he poin s o P om p1 o pj+1 and he poin s o Q om qj o qn ). The e o e, in he  s isi o he else b anch asse ion (2) is ue. Suppose ha he las illegal iangle explo ed is qj1pi1pi1+1 and he algo i hm is explo ing a new il- legal iangle qjpipi+1 . As (2) was ue in he p e- ious i e a ions, poin qj1 has o be placed be ween qj1−1 and he  s c ossing o line pi1pi1+1 wi h Q . A e explo ing his iangle, subsc ip j1 is inc eased by one, and hen h ope a ions (pe haps h= 0 ) o inc easing bo h subsc ip s ( i and j ) a e done. The e- o e, i mus be j=j1+h+ 1 and i=i1+h , o some h≥0 . Since (1) is in a ian , he h+ 1 iangles qj−1pi−1pi, qj−2pi−2pi−1, . . . , qj1pi1−1pi1 a e legal. The e o e, i qj is placed a e he second c oss- ing o line pipi+1 wi h Q , hen, by emo ing he h poin s o Q om qj1+1 o qj−1 , he h+ 2 poin s o P om pi1+1 o pi+1 appea in he bounda y o he new con ex hull, con adic ing he U-condi ion (see Figu e 3 igh ). Hence, (2) is in a ian . Las ly, since (1) is in a ian and he las iangle, qj−(i−1)p1p2 , is legal, hen he subsc ip j−i+ 1 has o be be ween 1 and m . This implies ha j≤i+m−1 in he algo i hm. Hence, he al- go i hm can go o he else b anch a maximum o m−1 imes, and nishes in a maximum numbe o n+m−1 s eps. When he algo i hm nishes, hen i=n+ 1 and he iangles o he sequence qj−1pnpn+1, qj−2pn−1pn, . . . , qj−np1p2 a e legal be- cause (1) is in a ian .  Now, assume ha |Q|=|P| , Q∪P sa ises he U-condi ion, he e a e mo e poin s inside P and ha |Q|>3 ( he case |Q|= 3 was sol ed in [2]). To ge a 4-connec ed geome ic g aph, we p oceed as ollows. Fi s d aw he zig-zag including al e na i ely he poin s o P and Q , acco ding o he p e ious lemma. Then, ake a diagonal o P , o example diagonal p1p3 . This diagonal di ides P in o wo subpolygons P1= {p1, p3, . . . , pn, p1} and P0 1={p1, p2, p3, p1} . I he in- e io I(P1) o P1 is nonemp y, hen le P2 be he con- ex polygon dened by he poin s H(I(P1)∪p1, p3) . I he in e io I(P2) o his polygon is again nonemp y, 125 On 4-connec ed geome ic g aphs hen we dene P3 as he con ex polygon dened by he poin s H(I(P2)∪p1, p3) , and so on, un il we ob- ain an emp y con ex polygon Ph . Thus, we ha e a sequence Ph⊂Ph−1⊂. . . ⊂P2⊂P1 o nes ed polygons (see Figu e 4 le ). The same p ocess can be done s a ing a P0 1 , ob aining ano he sequence P0 h0⊂P0 h0−1⊂. . . ⊂P0 2⊂P0 1 o nes ed polygons. Obse e ha he egion Mi ( M0 i ) bounded by he con- secu i e polygons Pi+1 and Pi ( P0 i+1 and P0 i ) has he shape o a hal -moon. I is no dicul o p o e ha Mi ( M0 i ) can be iangula ed such ha poin s p1 and p3 a e no used, and each one o he added edges has an endpoin in Pi ( P0 i ) and he o he one in Pi+1 ( P0 i+1 ). Then, we iangula e all he hal -moons in his way (using edges connec ing poin s placed in die en polygons) and we iangula e he con ex polygon P , o med by conca ena ing Ph and P0 h0 , such ha he only poin s wi h deg ee wo a e p1 and p3 . I can be easily checked ha he iangula ion ob ained in his way is 4-connec ed (see Figu e 4 igh ). p1 p2 p3 Q P1 P2 p1 p2 p3 Q P0 1 p4 p5 p6 p7 p8 Figu e 4: The gene al cons uc ion when |Q|=|P| and he e a e poin s inside P . The case in which |Q|<|P| and Q∪P sa ises he U-condi ion is sol ed in a simila way. Fi s a g aph based on a zig-zag is buil , al hough his s a - ing g aph canno be a zig-zag as in he p e ious case, because |Q|<|P| . Now, he s a ing g aph is a zig- zag connec ing he poin s o Q o some poin s o P plus some addi ional edges connec ing he poin s o P no belonging o he zig-zag o some poin s o Q (bold edges in Figu e 5 le ). A e building his s a ing g aph, we ake a diagonal o P connec ing wo poin s o P , consecu i e in he zig-zag bu no consecu i e in P (poin s pi1 and pi2 in Figu e 5), and we p oceed as in he p e ious case, adding he iangula ions o he die en hal -moons and he nal iangula ion o he con ex polygon P (see Figu e 5 igh ). The esul ing iangula ion is 4-connec ed. The U-condi ion is he key o nding his s a ing g aph ( he zig-zag plus some addi ional edges), al- hough p o ing he exis ence o such a g aph is no ob ious. Due o space limi a ions, we do no include his p oo . The e o e, we ha e p o ed he ollowing heo em. Theo em 4 Le S be a se o poin s. I Q=H(S) , P=H(S Q) and Q∪P sa ises he U-condi ion, Q pi1 pi2 pi3 pi4 pi5 P Figu e 5: The gene al cons uc ion when |Q|<|P| and he e a e poin s inside P . hen S is 4-connec ible. 3 Conclusions In his pape , we ha e dened a condi ion, he U- condi ion, ha any se o poin s S mus sa is y o be 4-connec ible. Mo eo e , we ha e p o ed ha he U- condi ion is also sucien o se s o poin s in which Q∪P sa ises he U-condi ion. In [2], he case |Q|= 3 is comple ely sol ed. Gi en a se S o poin s such ha |Q|= 3 , he au ho s show how o build a 4-connec ed iangula ion on S , excep o a pa icula congu a ion o poin s. This pa icu- la congu a ion is p ecisely he only one no sa is y- ing he U-condi ion, among all he congu a ions o poin s such ha |Q|= 3 . Using die en echniques no included in his pa- pe , we can ex end he amily o 4-connec ible se s. Fo any se S o poin s sa is ying he U-condi ion (i is no equi ed ha Q∪P sa ises he U-condi ion) such ha |P|= 3 o |P|= 4 , we can buil a 4-connec ed geome ic g aph on S . Finally, we conclude wi h he ollowing conjec u e. Conjec u e 1 I a se o poin s S sa ises he U- condi ion, hen S is 4-connec ible. Re e ences [1] P. B ass, W. Mose and J. Pach, Resea ch P oblems in Disc e e Geome y , Sp inge -Ve lag, Be lin, 2005. [2] T.K. Dey, M.B. Dillencou , S.K. Ghosh and J.M. Cahill, T iangula ing wi h high connec i i y, Com- pu . Geom. Theo y Appl. 8 (1997), 3956. [3] A. Ga cía, F. Hu ado, C. Hueme , J. Tejel and P. Val , On iconnec ed and cubic plane g aphs on gi en poin se s, Compu . Geom. Theo y Appl. 42 (2009), 913922. [4] J. Pach (ed.), Thi y Essays on Geome ic G aph Theo y , Sp inge Science+Business Media, New Yo k, 2013. 126