Information Technology Reference
In-Depth Information
its parent's one. Thus, we obtain a contact representation of
T
with circles. The repre-
sentation is balanced since the diameter for every circle is equal to the side-length for
its square and we started with a balanced representation
ʓ
.
The linear running time can be achieved by a linear-time traversal of
T
.First,bya
bottom-up traversal of
T
,wecompute the values
n
(
v
) and
l
(
v
) for each vertex
v
of
T
.
Using the values for each vertex, we compute the square-contact representation for
T
by a linear-time top-down traversal of
T
. Finally, in another top-down traversal of
T
,
for each vertex
v
of
T
, we can compute the exact translation required for the inscribed
circles of
R
(
v
) to touch the parent circle.
Let us now describe how to compute a balanced circle-contact representation for a
cactus
graph, which is a connected graph in which every biconnected component is
either an edge or a cycle. We use the algorithm described in the proof of Theorem 2,
and we call it
Draw Tree
.
Let
T
be a rooted tree with a plane embedding. For each vertex
v
of
T
,addan
edge between every pair of the children of
v
that are consecutive in the clockwise order
around
v
.Calltheresultinggraph an
augmented fan-tree
for
T
. Clearly for any rooted
tree
T
,theaugmented fan-tree is outerplanar. We call an outerplanar graph a
fan-tree
graph if it is an augmented fan-tree for some rooted tree. A
star
is the complete bipartite
graph
K
1
,n−
1
. The center of a star is the vertex that is adjacent to every other vertex.
An augmented fan-tree for a star is obtained by taking the center as the root. Thus, an
augmented fan-tree for a star is a
fan
.The
center
of a fan is again the vertex adjacent to
all the other vertices.
Lemma 3.
Every subgraph of a fan admits a contact representationwith circles in
which,foreach circle
c
(
v
)
representing a vertex
v
other than thecenter, the vertical
strip containing
c
(
v
)
is emptyabove
c
(
v
)
.
Proof:
Let
G
be a subgraph of a fan and let
T
be the star contained in the fan. We now
use the contact representation
ʓ
of
T
obtained by
Draw Tree
to compute a representa-
tion for
G
. Consider the square-contact representation computed for
T
in the algorithm.
This defines a vertical strip for each circle
c
(
v
) in
ʓ
representing avertex
v
,andforall
the vertices other than the center, these strips are disjoint; see Fig. 6(a). Call the left and
right boundary of this strip the
left-
and
right-line
for
c
, respectively.
We now consider a set
S
of circles, one for each vertex of
G
other than the center,
with the following properties:
(P1) The circles are interior-disjoint.
(P2) Each circle
c
(
v
) representing avertex
v
spans the entire width of the vertical strip
for
v
, and the vertical strip above
c
(
v
) is empty.
(P3) For each vertex
v
,thecircle
c
(
v
) touches the circle
c
0
representing the center in
ʓ
if
v
is adjacent to the center; otherwise,
c
(
v
) is exactly
ʵ
distance away from
c
0
, for some fixed constant
ʵ>
0.
(P4) If a vertex
v
is not adjacent to the vertex on its left (or if
v
is the leftmost vertex),
then the leftmost point of
c
(
v
) is on the left-line of
v
; similarly, if
v
is not adjacent
to the vertex on its right (or if
v
is the rightmost vertex), then the rightmost point
of
c
(
v
) is on the right-line of
v
.
