Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 4.
Planar graphs with no balanced circle-contact representation: (a) the nested-triangles
graph [8]; (b) a 2-outerplanar graph
of 1 to those leaves
v
that do not have any tree rooted at them; otherwise, if
v
is the root
of a tree
T
v
with label
l
+1,theweight of
v
is the total weight of
T
v
. The total weight
of
T
is defined as the summation of the weights of all its leaves.
Now, for each vertex
v
of
G
, the distance to
v
from the root
r
of
T
0
is
(
k
+log
n
).
Indeed, assume that
v
=
u
l
is a vertex with label
l
and
u
lā
1
,
...
,
u
1
,
u
0
=
r
are the
root vertices of the successive weight-balanced trees
T
u
lā
1
,
...
,
T
u
1
,
T
0
with labels
l
O
ā
1
,...,
1
,
0, respectively on the way from
v
to
r
;seeFig. 3. Then the distance from
v
to
r
is
O
(
log
w
(
r
)
/w
(
u
1
)
)+
O
(
log
w
(
u
1
)
/w
(
u
2
)
)+
...
+
O
(
log
w
(
u
lā
1
)
/w
(
v
)
)=
O
(
k
+log
w
(
r
)).Here
w
(
u
i
) denotes the weight of vertex
u
i
as the root;
w
(
r
) is the
weight of the root of
T
0
, which is equal to the total number of vertices,
n
,in
G
.There-
fore, the diameter of the augmented graph is
(
k
+log
n
), where the first term,
k
,
comes from the ceilingsinthesummation. Finally, we triangulate the graph by insert-
ing outerpaths with constant maximumdegree inside each non-triangular face to obtain
a maximal planar graph with constant maximumdegree and
O
O
(
k
+log
n
) diameter. The
result follows from Lemma 1.
2.2
Negative Results
Next we show that, for a graph with unbounded maximumdegree or unbounded outer-
planarity, there might not be a balanced circle-contact representation with circles.
Lemma 2.
There is nobalanced circle-contact representation for the graphsin Fig.4.
Lemma 2, which we prove in the full version of this paper [1], shows the tightness
of the two conditions for balanced circle-contact representations in Theorem 1. Note
that the example of the graph in Fig. 4(b) can be extended for any specified maximum
degree, by adding a simple path to the high-degree vertex. Furthermore, the example is
a 2-outerplanar graph with no balanced circle-contact representation.
