Cover Contact Graphs

Co e Con ac G aphs Nie es A ienza2,, Na alia de Cas o2,, Ca men Co ´es2,, M. ´ Angeles Ga ido2,, Cla a I. G ima2,, G ego io He n´andez1, Albe o M´a quez2,, Auxiliado a Mo eno2,,Ma inN¨ollenbu g3,, Jos´e Ramon Po illo2,,Ped oReyes 2,,Jes´us Valenzuela2,, Ma ia T inidad Villa 2,, and Alexande Wolff4 1Dep . Ma em´a ica Aplicada, Fac. In o m´a ica, Uni . Poli ´ecnica de Mad id, Spain [email p o ec ed] 2Uni e sidad de Se illa, Spain {na ienza, na alia, cco es, izue e, g ima, alma , auxiliado a, jose a, p eyes, jesus , illa }@us.es 3Fakul ¨a ¨u In o ma ik, Uni e si ¨a Ka ls uhe, Ge many [email p o ec ed] 4Facul ei Wiskunde en In o ma ica, TU Eindho en, The Ne he lands h p://www.win. ue.nl/~awol Abs ac . We s udy p oblems ha a ise in he con ex o co e ing ce - ain geome ic objec s (so-called seeds, e.g., poin s o disks) by a se o o he geome ic objec s (a so-called co e , e.g., a se o disks o homo- he ic iangles). We insis ha he in e io s o he seeds and he co e elemen s a e pai wise disjoin , bu hey can ouch. We call he con ac g aph o a co e a co e con ac g aph (CCG). We a e in e es ed in wo ypes o asks: (a) deciding whe he a gi en seed se has a connec ed CCG, and (b) deciding whe he a gi en g aph has a ealiza ion as a CCG on a gi en seed se . Conce ning ask (a) we gi e efficien algo i hms o he case ha seeds a e poin s and co e s a e disks o iangles. We show ha he p oblem becomes NP-ha d i seeds and co e s a e disks. Con- ce ning ask (b) we show ha i is e en NP-ha d o poin seeds and disk co e s (gi en a fixed co espondence be ween e ices and seeds). 1 In oduc ion Koebe’s heo em [9,11], a beau i ul and classical esul s in g aph heo y, says ha e e y plana g aph can be ep esen ed as a coin g aph, i.e., a con ac g aph o disks in he plane. In o he wo ds, gi en any plana g aph wi h n e ices, he e is a se o ndisjoin open disks in he plane ha a e in one- o-one co espondence o he e ices such ha a pai o disks is angen i and only i he co esponding e ices a e adjacen . Koebe’s heo em has been edisco e ed se e al imes, see he su ey o Sachs [12]. Collins and S ephenson [4] gi e an efficien algo i hm o nume ically app oxima ing he adii and loca ions o he disks o such a Pa ially suppo ed by p ojec s PAI FQM—0164 and ORI MTM2005-08441-C02-01.  Suppo ed by g an WO 758/4-2 o he Ge man Resea ch Founda ion (DFG). S.-H. Hong, T. Nishizeki, and W. Quan (Eds.): GD 2007, LNCS 4875, pp. 171–182, 2007. c Sp inge -Ve lag Be lin Heidelbe g 2007 172 N. A ienza e al. (a) disk seeds (b) disk co e o (a) (c) CCG induced by (b) Fig. 1. Seeds, co e , and CCG ep esen a ion o a plana g aph. Thei algo i hm elies on an i e a i e p ocess sugges ed by Thu s on [13]. Since Koebe he e has been a lo o wo k in he g aph-d awing communi y dedica ed o he ques ion which plana g aphs can be ep esen ed as con ac o in e sec ions g aphs o which geome ic objec . As a ecen example, F aysseix and Ossona de Mendez [5] showed ha any ou -colo ed plana g aph wi hou an induced ou -colo ed C4is he in e sec ion g aph o a amily o line segmen s. On he o he hand, he e has been a lo o wo k in he geome ic-op imiza ion communi y dedica ed o he ques ion how o (op imally) co e geome ic objec s (usually poin s) by o he geome ic objec s (like con ex shapes, disks, annuli). As an example ake Welzl’s amous andomized algo i hm [15] o finding he smalles enclosing ball o a se o poin s. In his pape we combine he wo p e ious p oblems: we a e looking o ge- ome ic objec s (like disks o iangles) whose in e io s a e disjoin , ha co e gi en pai wise disjoin objec s called seeds (like poin s o disks) and a he same ime ep esen a gi en g aph o g aph p ope y by he way hey ouch each o he . O he han in geome ic op imiza ion each o ou co e ing objec s con ains only one o he seeds. We a e no in e es ed in maximizing he sizes o he co e ing objec s; ins ead we wan hem o join ly ulfill some g aph- heo e ic p ope y (like connec i i y). Compa ed o p e ious wo k on geome ic ep esen a ion o g aphs we a e mo e es ic ed in he choice o ou ep esen a i es. Le us ge a bi mo e o mal. Gi en a se So pai wise disjoin seeds o some ype, a co e o Sis a se Co closed objec s o some ype wi h he p ope y ha each objec con ains exac ly one seed and ha he in e io s o no wo objec s in e sec . Figu e 1b depic s a disk co e o he disk seeds in Figu e 1a. Now he co e con ac g aph (CCG) induced by Cis he con ac g aph o he elemen s o C. In o he wo ds, wo e ices o a CCG a e adjacen i he co esponding co e elemen s ouch, i.e., hei bounda ies in e sec . Figu e 1c depic s he CCG induced by he co e in Figu e 1b. No e ha he e ices o he CCG a e in one- o-one co espondence o bo h seeds and co e elemen s. We conside seeds o be opologically open (excep i hey a e single poin s). Then seeds can ouch each o he . (No e ha we equi e co e objec s o be closed. This makes su e ha a co e ac ually con ains a poin seed ha lies on i s bounda y.) In his pape we in es iga e he ollowing ques ions. Connec i i y: Gi en a seed se , does i ha e a (1- o 2-) connec ed CCG? Co e Con ac G aphs 173 Realizabili y: Gi en a plana g aph and a se o seeds, can he gi en g aph be ealized as a CCG on he gi en seeds? A hi d ype o ques ion is ea ed in he long e sion o his a icle [3]: Enume a ion: Fo a gi en numbe o e ices, how many g aphs o a ce ain g aph class can be ealized as a CCG? Howe e , we do conside in his pape an in e es ing es ic ion o he abo e p oblems whe e seeds and co e elemen s mus lie in he hal plane R2 +abo e and including he x-axis. Seeds a e addi ionally es ic ed in ha each mus con ain a leas one poin o he x-axis. In his es ic ed se ing we call he con ac g aph o a co e a CCG+. See Figu es 7b and 9 o examples. Ou esul s. Fi s , we conside a bi a y se s o poin seeds, see Sec ion 2. Con- ce ning connec i i y we show ha we can always co e a se o poin seeds using disks o using homo he ic iangles such ha he esul ing CCG is 1- o e en 2-connec ed. Ou algo i hms un in O(nlogn) expec ed and O(n2) wo s -case ime, espec i ely. Conce ning ealizabili y we gi e some necessa y condi ions and hen show ha i is NP-ha d o decide whe he a gi en g aph can be e- alized as a disk-CCG i he co espondence be ween e ices and poin seeds is gi en. Second, we conside he es ic ion whe e we a e gi en a se So poin s on he x-axis as seeds. We show ha in his case 1-connec i i y is easy: we can ealize Cnas a CCG on Sand he e a e ees ha can be ealized as a CCG+on S. Fo he case ha he co espondence be ween seeds and e ices is gi en, we gi e an algo i hm ha decides in O(nlogn) ime which ees can be ealized as CCG+. Thi d, we conside disk seeds, see Sec ion 4. We show ha e en deciding whe he a se o disk seeds has a connec ed disk-CCG is NP-ha d. We can only ske ch p oo s he e. We e e he eade o he long e sion [3] o his pape . Rela ed wo k. Abellanas e al. [1] p o ed ha he ollowing p oblem, which hey call he coin placemen p oblem, is NP-comple e. Gi en ndisks o a ying adii and npoin s in he plane, is he e a way o place he disks such ha each disk is cen e ed a one o he gi en poin s and no wo disks o e lap? Abellanas e al. [2] conside ed a ela ed p oblem. They showed ha gi en a se o poin s in he plane, i is NP-comple e o decide whe he he e a e disjoin disks cen e ed a he poin s such ha he con ac g aph o he disks is connec ed. Gi en a pai o ouching (con ex) co e elemen s, we can d aw he co e- sponding edge in he CCG by a wo-segmen polygonal line ha connec s he inciden seeds and uses he con ac poin o he co e elemen s as bend. This is a link o he p oblem o poin -se embeddabili y. We say ha a plana g aph G is k-bend (poin -se ) embeddable i o any poin se P⊂R2 he e is a one- o- one co espondence be ween Vand Psuch ha he edges o Gcan be d awn as non-c ossing polygonal lines wi h a mos kbends. Kau mann and Wiese [8] showed ha (a) e e y 4-connec ed plana g aph is 1-bend embeddable, (b) e e y plana g aph is 2-bend embeddable, and (c) gi en a plana g aph G=(V,E) and a se Po npoin s on a line, i is NP-comple e o decide whe he Ghas a 1-bend embedding ha maps Vone- o-one on P. 174 N. A ienza e al. 2 The Seeds A e Poin s in he Plane In his sec ion we s udy poin seeds which may ake any posi ion in he plane. I no s a ed o he wise ou esul s hold o bo h disk co e s and (homo he ic) iangle co e s. We ocus on he wo ques ions aised be o e: connec i i y and ealizabili y. 2.1 Connec i i y I is known o be NP-ha d o decide whe he a gi en se o poin s can be co e ed by a se o pai wise disjoin open disks, each cen e ed on a poin , such ha he con ac g aph o he disks is connec ed [2]. In con as o ha esul we gi e a simple sweep-line algo i hm ha co e s poin seeds by (non-cen e ed) disks such ha hei con ac g aph is connec ed. P oposi ion 1. E e y se So npoin seeds has a connec ed CCG. Such a CCG can be cons uc ed in O(nlog n) ime and linea space. P oo . A e so ing Sby dec easing o dina e we p oceed inc emen ally om op o bo om. Fo he fi s poin , we place a co e elemen (disk o iangle, depending on he case) o fixed size wi h he seed as i s bo ommos poin . I he k−1 opmos poin s a e al eady connec ed, hen o he k- h poin pwe infla e a co e elemen Cpwi h pas he bo ommos poin un il Cp ouches one o he p e iously placed co e elemen s. The implemen a ion o disk-CCGs is simila o Fo une’s sweep [6] o con- s uc ing he Vo onoi diag am o a se o weigh ed poin s. Fo iangle-CCGs we epea edly de e mine he size o he new iangle in O(log n) imebyasegmen - d agging que y [10] and wo e y simple ay-shoo ing que ies.  In ac , e en mo e can be ob ained as he ollowing p oposi ion assu es. P oposi ion 2. Any se So npoin seeds has a biconnec ed CCG. Such a CCG can be cons uc ed in O(n2logn) ime using linea space. P oo . We fi s conside disks as co e elemen s. Le D1,D2,andD3be h ee cong uen disks ha ouch each o he . They delimi a pseudo- iangula shape R. Choose he h ee disks such ha each disk Dicon ains a unique poin pi∈S and such ha S {p1,p 2,p 3}⊂R, see Figu e 2 (le ). In o de o co e he emaining poin s we assume ha disks D4,...,D i−1ha e been placed such ha each co e s a unique poin o Sand ouches wo p e iously placed disks, see Figu e 2 (middle). Thus he con ac g aph o D1,...,D i−1is biconnec ed. Le Rjbe a connec ed componen o R i−1 j=4 Di ha con ains a leas one unco e ed poin . Use Fo une’s sweep [6] o compu e he combined Vo onoi diag am o he disks inciden o Rjand he poin s in S∩Rj.This akes O(nlog n) ime and he esul ing Vo onoi diag am has complexi y O(n). The pa o he Vo onoi diag am in Rjis he locus o he cen e s o all disks ha lie in Rjand ouch ∂Rj∪(S∩Rj)ina leas wopoin s,whe e∂Rjis he bounda y o Rj. Now we make a simple bu c ucial obse a ion: i Dis a disk ha (a) lies Co e Con ac G aphs 175 D1D2 D3 p1 p3 R p2 D1D2 D3 p1 p3 p4 D4 R7 p5 p6 p2 D1D2 D3 p1 p2 p3 p4 p7 p8 D8 D4D7 R9 p5 p6 Fig. 2. Th ee s eps in he cons uc ion o a biconnec ed disk-CCG in Rj, (b) con ains a seed s∈S∩Rjon i s bounda y, and (c) ouches wo o he p e ious disks, hen Dis cen e ed a a e ex o he Vo onoi diag am. Thus a disk D ulfilling (a)–(c) can be ound in linea ime and, by cons uc ion, does no con ain any poin o Sin i s in e io . (I by any chance all such disks ouch mo e han one poin o S, we e-s a he whole compu a ion wi h h ee sligh ly wiggled ini ial disks D1,D2,andD3. Then he p obabili y o his degene acy becomes 0.) Now se Di=D, and epea he p ocess un il all seeds a e co e ed. This akes O(n2logn) ime in o al. The case o iangles can be handled analogously. Choosing any e e ence poin in he iangula shape, a s uc u e simila o he medial axis can be compu ed in O(nlogn) and upda ed in O(n) imeineacho hen−3 phases.  2.2 Realizabili y In his sec ion we fi s gi e wo necessa y condi ions ha a plana g aph mus ulfill in o de o be ealizable as a disk-CCG on a gi en seed se . Then we cons uc a plane geome ic g aphs on six e ices ha canno be ep esen ed as disk-CCG. Finally we in es iga e he complexi y o deciding ealizabili y. To o mula e ou necessa y condi ions o ealizabili y we define a g aph on he gi en seed se S. Ou g aph is inspi ed by he sphe e-o -influence g aph defined by Toussain [14]. Gi en a seed se Sand a poin p∈Sle he influence a ea o pbe he closu e o he union o all emp y open disks D(i.e., D∩S=∅) ha a e cen e ed a e ices o he Vo onoi egion o p, see Figu e 3. We call he in e sec ion g aph o hese influence a eas he hype influence g aph o Sand deno e i by HI(S), see Figu e 4. P oposi ion 3. Le Sbe a se o poin seeds and le Gbe a g aph ealizable as a disk-CCG on S.Then (i) Gis a subg aph o HI(S),and (ii) Ghas a plane d awing whe e each e ex is mapped o a unique poin in S and each edge is d awn as a polygonal line wi h a mos wo segmen s (i.e., wi h a mos one bend pe edge). 176 N. A ienza e al. p p6 p7 p1 p2 p3 p4 p5 Fig. 3. Influence a ea o p∈S(shaded) p p6 p7 p1 p2 p3 p4 p5 Fig. 4. The hype influence g aph HI(S) P oo . Bo h ac s a e s aigh o wa d o ob ain. (i) is based on he obse a ion ha any possible co e ing disk o pis con ained in he influence a ea o p.Thus, i he co e ing disks o wo seeds a e in con ac , hei influence a eas in e sec . (ii) is ob ained by ep esen ing each edge o he CCG by wo line segmen s ha connec he seeds wi h he poin o angency o he co e ing disks.  While P oposi ion 3 (ii) is difficul o e i y e en i all seeds lie on a line [8], P oposi ion 3 (i) gi es us a way o show non- ealizabili y o ce ain geome ic g aphs as he one depic ed in Figu e 5. Tha g aph is connec ed and hus canno be ealized as a CCG wi h i s e ices as seeds, because he shaded influence a eas o p1and p2do no in e sec . The g aph has eigh e ices. On he o he hand i is easy o see ha any h ee- e ex g aph can be ealized on any h ee-poin seed se . Now i is in e es ing o ask o he leas n o which he e is an n- e ex geome ic g aph Gsuch ha he s aigh -line d awing o Gis plane bu Gcanno be ealized as CCG. p1p2 Fig. 5. Non- ealizable bipa i e g aph We show ha he e is a se S={a,b,..., }o six poin s in con ex posi ion such ha hei Delaunay ian- gula ion is no ep esen able as a CCG, see he unde lying g aph in Figu e 6. The co e ing disks Daand Ddo he poin s aand dmus ouch each o he in one o wo ways. Ei he he angen poin o he disks lies inside he con ex hull o S,o Daand Dda e e y la ge and lie o he le o aand o he igh o d, in which case hey ouch a abo e o below S,see Figu e 6. In he fi s case he e is no disk co e ing cand ouching Da.In he second case we can assume ha he bounda ies o Daand Dda e wo almos pa allel lines in he icini y o he six poin s. The disks Dcand D co e ing c and mus bo h ouch Daand Dd.Bu i cand a e close enough o aand d hen Dcand D canno be disjoin . So we ha e seen ha he e a e pai s o (qui e small) g aphs and seed se s such ha he g aph canno be ealized on heseedse asdiskCCG.Thuswewould like o decide whe he a gi en g aph is ealizable as CCG on a gi en seed se o no . O cou se Koebe’s heo em [9] gua an ees ha o any plana g aph G we can find a seed se Ssuch ha i is possible o ealize Gon S. Howe e , i Co e Con ac G aphs 177 a bc d e a bc d e DaDd DaDd Dc D . . .. . . . . .. . . Fig. 6. Non- ealizable Delaunay iangula ion o six poin s in con ex posi ion he seeds and he e ex–seed co espondence a e gi en, he p oblem becomes NP-ha d. Theo em 1. Gi en a se So poin s in he plane and a plana g aph G=(S, E), i is NP-ha d o decide whe he Gis ealizable as disk-CCG on S. The p oo is by educ ion om he NP-ha d p oblem Plana 3SAT.The e a e gadge s o each a iable and each clause o he gi en Boolean o mula. The gadge o a a iable is such ha i allows wo combina o ially diffe en ways o ep esen he gi en subg aph as disk-CCG. These co espond o he wo Boolean alues o . The clause gadge is locally symme ic wi h espec o 120◦- o a ions and designed such ha some co e disks mus o e lap i and only i he co esponding h ee li e als a e all alse. 3 The Seeds A e Poin s on a Line In his sec ion, seed se s consis o poin s on he x-axis. Connec i i y ollows om some o ou ealizabili y esul s, so we ocus on he la e . We conside he ollowing ou ques ions. No e ha seeds now co espond o eal numbe s, so we can use he na u al o de <in R o compa e hem. All co e s consis o disks unless s a ed o he wise (e.g., in Q4). Q1. Gi en a g aph class C(e.g., he class o ees), does i hold ha o any seed se S he e is a g aph in C ha is ealizable as CCG o CCG+on S? We show: This is ue o (cycles, CCG) and ( ees, CCG+). Q2. Gi en a g aph class C, does i hold ha o any g aph Gin C he e is a seed se Ssuch ha Gcan be ealized as CCG o CCG+on S? We show: This is ue o he combina ion ( ees, CCG+). Q3. Le Cbe a fixed g aph class. Gi en a g aph G∈Cwi h a labeling λ:V→ {1,...,n}, is he e a sequence s1<...<s no seeds in R1and a ealiza ion o G ha maps each e ex o he co esponding seed sλ( )? We show: The e is an O(nlog n) decision algo i hm o ( ees, CCG+). 178 N. A ienza e al. x ad bc DaDd  (a) Cnis ealizable as CCG CCG+o S ee T(S) D (b) ee T(S) is ealizable as CCG+ Fig. 7. G aphs ha can be ealized on a gi en one-dimensional n-poin seed se S Q4. Le Cbe a fixed g aph class. Gi en a seed se Sand a g aph G(S, E)∈C, can Gbe ealized on Sas iangle CCG o CCG+? We show: The e is an O(nlog n)- ime decision algo i hm o ( ees, CCG+). No e ha he abo e ques ions equi e mo e and mo e conc e e in o ma ion abou he seed se , anging om no in o ma ion (Q2) ia a fixed o de (Q3) o comple e in o ma ion (Q4). We s a wi h ques ion Q1. P oposi ion 4. Le Sbe a se o npoin seeds on a line, hen (i) he n- e ex cycle Cncan be ealized as CCG on S,and (ii) he e is a ee T(S) ha can be ealized as CCG+on S. Figu es 7a and 7b gi e some in ui ion abou how ou algo i hms wo k; o de ails see he long e sion o his pape [3]. In e ms o his pape , a coin g aph is ob ained when seeds a e poin s and co e elemen s a e disks cen e ed a seeds, and hus Koebe’s heo em es ablishes ha i is always possible o choose seeds in he plane such ha any gi en plane g aph is ealizable as a coin g aph on hem. We ha e seen in P oposi ion 4 ha Cnis ealizable as a CCG on any seed se on a line. One can ask whe he a Koebe- ype heo em also holds in his es ic ed se ing. Howe e , Kau mann and Wiese [7] ha e shown ha he e is a plane iangula ed 12- e ex g aph (see Figu e 8) ha canno be d awn wi h only one bend pe edge i e ices a e es ic ed o a line. Now P oposi ion 3 (ii) implies ha ha g aph is no ealizable as CCG i seeds lie on a line. On he posi i e side, we can show ha a Koebe- ype heo em holds o he combina ion ( ees, CCG+). This is an answe o Q2 and in a way dual o P oposi ion 4 (ii). See Figu e 9 o a ske ch o ou ecu si e cons uc ion. P oposi ion 5. Fo any ee T he e is a seed se S(T)⊂R1such ha Tis ealizable as CCG+on S(T). Co e Con ac G aphs 179 1 2 3 D0 D1 D2 D3 0 1 2 3 R2R110 Fig. 8. Kau mann–Wiese g aph [8] Fig. 9. Cons uc ing a seed se S(T) In P oposi ion 5 abo e, we had comple e eedom o choose he seeds. Now we u n o ques ion Q3, whe e we a e no jus gi en a ee, bu also an o de o i s e ices ha mus be espec ed by he co esponding seeds. Kau mann and Wiese [7] ha e in es iga ed a ela ed p oblem. They showed ha i is NP-comple e o decide whe he he e ices o a gi en (plana ) g aph can be pu in o one- o-one co espondence wi h a gi en se o poin s on a line such ha he e is a plane d awing o he g aph wi h a mos one bend pe edge. We call such a d awing a 1d-1BD. I addi ionally all bends lie on one side o he line, we call he d awing a1d-1BD +. No e ha he ha dness esul o Kau mann and Wiese does no yield he ha dness o he one-dimensional CCG ealizabili y p oblem, since no e e y g aph ha can be one-bend embedded on a se o poin s on a line is ealizable as CCG, le alone as CCG+. Ou nex esul explo es he gap be ween Kau - mann and Wiese’s one-dimensional embeddabili y p oblem and he si ua ion in P oposi ion 5. Mo e o mally, gi en an n- e ex ee Tand a (bijec i e) labeling λ:V→ {1,...,n}o i s e ices, we say ha Tis λ- ealizable (as CCG, CCG+,1d- 1BD, 1d-1BD+) i he e is a sequence s1< ... < s no seeds in R1and a ealiza ion o T(as CCG, CCG+, 1d-1BD, 1d-1BD+) ha mapseach e ex o he co esponding seed sλ( ). In o de o ob ain a cha ac e iza ion o ees ha a e λ- ealizable as CCG+,we need he ollowing defini ion. Gi en a g aph G=(V,E) wi h e ex labeling λ, a o bidden pai is a pai o edges {a, b},{c, d}such ha λ(a)<λ(c)< λ(b)<λ(d). No e ha i is impossible o embed he edges o a o bidden pai simul aneously abo e he x-axis. Theo em 2. Fo a λ-labeled ee T he ollowing s a emen s a e equi alen : (i) Tis λ- ealizable as a CCG+. (ii) Tis λ- ealizable as a 1d-1BD+. (iii) Tdoes no con ain any o bidden pai . Gi en he ee, s a emen (iii) can be checked in O(nlog n) ime using an in e al ee, he e o e he ollowing co olla y is s aigh o wa d.