Information Technology Reference
In-Depth Information
1
2
3456
7
1 2
34
56
7
p
p
3
5
1
4
345
6
2
6
2
1
7
7
ʵ
p
p
(a)
(b)
Fig. 6.
(a) A star
T
and a contact representation of
T
with circles; (b) a subgraph of the fan for
T
and its contact representation with circles
(P5) The sizes for the circles are maximal with respect to the above properties.
Note that there exists a set of circles with the properties (P1)-(P4); in particular,
the set of circles in
ʓ
representing the vertices of
T
other than the center is such a
set. We now claim that the set
S
of circles with properties (P1)-(P5) together with the
circle
c
0
gives a contact representation for
G
;seeFig. 6(b). First note that a circle
c
(
v
)
cannot touch any circle other than
c
0
and the two circles
c
(
v
l
) and
c
(
v
r
) representing
the vertices
v
l
and
v
r
on its left and right, respectively. Indeed, it cannot pass the vertical
strip for
v
l
and
v
r
above them dueto(P2) and behind them dueto(P3). Furthermore,
the
ʵ
distance between
c
0
and the circles for vertices non-adjacent to the center and
the restriction on the left and right side in (P4) ensures that there is no extra contact.
Hence, it is sufficient to show that for each edgein
G
, we have the contact between the
corresponding circles.
Since each circle
c
(
v
) is maximal in size, it must touch at least three objects. One of
them is either the circle
c
0
or the
ʵ
offset line for
c
0
.Thus, if
v
l
and
v
r
are the left and
right neighbors of
v
(if any), then
c
(
v
) must touch two of the followings: (i)
c
(
v
l
) (or
the left line of
v
if
v
l
does not exists), (ii) the right line for
v
l
, (iii)
c
(
v
r
) (or the right line
of
v
if
v
r
does not exists), and (iv) the left line for
v
r
.Assume withoutlossofgenerality
that both
v
l
and
v
r
exist for
v
.Thenif
c
(
v
) touches both
c
(
v
l
) and
c
(
v
r
),wehavethe
desired contacts for
v
. Therefore, for a desired contact of
c
(
v
) to be absent, either
c
(
v
)
touches both
c
(
v
l
) and the right-line of
v
l
(and misses the contact with
c
(
v
r
)), or it
touches both
c
(
v
r
) and the left-line of
v
r
(and misses the contact with
c
(
v
r
)).
Assume, for the sake of a contradiction, that there are two consecutive vertices
x
and
y
that are adjacent in
G
but
c
(
x
) and
c
(
y
) do not touch each other. Let
l
and
r
be the
vertices to the left of
x
and to the right of
y
, respectively. Then it must be the case that
x
touches both
c
(
l
) and the right line for
l
and
y
touches both
c
(
r
) and the left line of
r
;seeFig. 7(a). One can then increase the size of either
c
(
x
) or
c
(
y
) (say
c
(
y
))such
