Information Technology Reference
In-Depth Information
d
=
(
k
log
n
), which does not yield a balanced circle-contact representation when
k
is non-constant. For
k
=
ʩ
(log
n
), we present a different augmentation to achieve the
diameter
d
=
O
(
k
+log
n
) in the resultinggraph.
We augment the graph using
weight-balanced binary trees
.Let
T
be a binary tree
with leaves
l
1
,l
2
,...,l
|f|
and a prespecified weight
w
i
assigned to each leaf
l
i
.The
tree
T
is
weight-balanced
if the depth of each leaf
l
i
in
T
is
O
),where
W
=
i
=1
w
i
. There exist several algorithms for producing aweight-balanced binary
tree with positive integer weights defined on its leaves [13, 21].
To augment
G
, we label each vertex
v
of
G
with the number
l
+1,where
l
is the
number of outer cycles that need to be removed before
v
becomes an outer vertex. By
ourassumption that the outerplanarity of
G
is
k
, the label of every vertex is at most
k
.
It follows from this labeling that, for each vertex
v
of
G
with label
l>
1, there exists
a face
f
containing
v
such that
f
has at least one vertex of label
l
O
(
log(
W/w
i
)
−
1 and such that
all the vertices on
f
have label either
l
or
l −
1.Weinsertaweight-balanced binary
tree inside
f
; we choose an arbitrary vertex of
f
with label
l −
1 as the root of the tree,
and a subset of vertices with label
l
as the leaves; see Fig. 3. We construct these trees
inside the different faces in such a way that each vertex of
G
with label
l>
1 becomes
a leaf in exactly one of the trees. Finally, we insert another weight-balanced tree
T
0
on
the outer face containing all the outer vertices as the leaves. Note that we have yet to
specify the weights we assign to these leaves for producing the weight-balanced trees.
By the construction, the union of all these trees forms a connected spanning tree of
G
;
we can consider the root of
T
0
to be the root of the whole spanning tree.
Let us now specify the weights assigned to the leaves of the different weight-balanced
trees. We label each tree with the label of its root, and define the weights for the leaves
of each tree in a bottom-upordering, by decreasing order of the labels of the trees. In
atree
T
with label
l
=(
k
1), all the leaves have label
k
and are not the root of any
other tree; we assign each of these leave the weight 1. In this case, the total weight of
T
is the number of its leaves. Similarly, for a tree with label
l<k
−
−
1, we assignaweight
r
u
1
level 1
u
2
level 2
u
3
level 3
Fig. 3.
Augmentation of
G
with a weight-balanced binary trees
