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