On Triangle Cover Contact Graphs

Let

S

 = {

p

1

,

p

2

,…,

p

n

} be a set of pairwise disjoint geometric objects of some type in a 2

D

plane and let

C

 = {

c

1

,

c

2

,…,

c

n

} be a set of closed objects of some type in the same plane with the property that each element in

C

covers exactly one element in

S

and any two elements in

C

are interior-disjoint. We call an element in

S

a

seed

and an element in

C

a

cover

. A

cover contact graph (CCG)

has a vertex for each element of

C

and an edge between two vertices whenever the corresponding cover elements touch. It is known how to construct, for any given point seed set, a disk or triangle cover whose contact graph is 1- or 2-connected but the problem of deciding whether a

k

-connected

CCG

can be constructed or not for

k

 > 2 is still unsolved. A

triangle cover contact graph (TCCG)

is a cover contact graph whose cover elements are triangles. In this paper, we give an algorithm to construct a 4-connected

TCCG

for a given set of point seeds. We also show that any outerplanar graph has a realization as a

TCCG

on a given set of collinear point seeds. Note that, under this restriction, only trees and cycles are known to be realizable as

CCG

.