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.