Information Technology Reference
In-Depth Information
a
a
c
a
c
c
d
b
b
d
b
d
h
i
h
i
m j
m
j
e
g
ef
g
p
e
g
l
f
h
i
j
k
o
k
n o
f
k
p
n
m
n
o
p
(a)
(b)
(c)
Fig. 5.
Construction of a balanced circle-contact representation
3
Trees and Outerplanar Graphs
Theorem 2.
Every tree has a balanced circle-contact representation. Sucharepresen-
tation can be foundin lineartime.
Proof:
We first find a contact representation
ʓ
of a given tree
T
with squares such that
the ratio of the maximum and the minimum sizes for the squares is polynomial in the
number of vertices
n
in
T
. To this end, we consider
T
as a rooted tree with an arbitrary
vertex
r
as the root. Then we construct a contact representation of
T
with squares where
each vertex
v
of
T
is represented by a square
R
(
v
) such that
R
(
v
) touches the square
for its parent by its top side and it touches all the squares for its children by its bottom
side; see Figs. 5(a) and 5(b). We choose the size of
R
(
v
) as
l
(
v
)+
ʵ
(
n
(
v
)
−
1),where
ʵ>
0 is a small positive constant and
n
(
v
) and
l
(
v
) denote the number of vertices and
the number of leaves in the subtree of
T
rooted at
v
. In particular, the size of
R
(
v
) is 1
when
v
is a leaf. If
v
is not a leaf, then suppose
v
1
,
...
,
v
d
are the children of
v
in the
counterclockwise order around
v
.Thenweplacethesquares
R
(
v
1
),
...
,
R
(
v
d
) from
left-to-right touching the bottom side of
R
(
v
) such that for each
i
,
R
(
v
i
+1
) is placed
ʵ
unit to the right of
R
(
v
i
);seeFig.5(b).Thereissufficient space
to place all these squares in the bottom side of
R
(
v
),since
n
(
v
)=(
i
=1
n
(
v
i
))
∈{
1
,...,d
−
1
}
−
1
and
l
(
v
)=
i
=1
l
(
v
i
). The representation contains no crossingsorunwanted contacts
since for each vertex
v
, the representation of the subtrees rooted at
v
is bounded in the
left and right side by the two sides of
R
(
v
), and all the subtrees rooted at the children
of
v
are in disjoint regions
ʵ
unit away from each other. The size of the smallest square
is 1, while the size of the largest square (for the root) has size
l
(
T
)+
ʵ
(
n
−
1) =
O
(
n
),
where
l
(
T
) is the number of leaves in
T
.
Using
ʓ
, we find a balanced circle-contact representation of
T
as follows. We replace
each square
R
(
v
), representing vertex
v
, by an inscribed circle of
R
(
v
);seeFig.5(c).
The operation removes some contacts from the representation. We re-create these con-
tacts by a top-down traversal of
T
and moving each circle upward until it touches its
parent. Note that a given circle will not touch or intersect any circle other than the cir-
cles for its parent and its children, as for every vertex in the infinite strip between its
leftmost and rightmost point for its circle, the closest circle in the upward direction is
