Information Technology Reference
In-Depth Information
to draw
G
bpq
such that
b,p,q
lie on
l
x
+3
,l
n
/
9
,l
x
+3
, respectively. On the other
hand, we use Lemma 2 and the Stretch condition to draw
G
abp
such that
a,b,p
lie on
l
1
,l
x
+3
,l
n
/
9
, respectively. Since
G
apq
≤
(
n
+2)
/
3, we can draw
G
apq
using Lemma 5 inside triangle
apq
. Figure 4(e) illustrates the scenario.
Case 2C (
leaf
(
T
a,G
abp
)
≤ n
/
9and
leaf
(
T
b,G
abp
)
>x
).
Since each of the
edges among (
a, b
)and(
b,p
) spans at least
n
/
9 + 2 parallel lines in Case 2B,
the drawing in this case is analogous to Case 2B. The only difference is that
we use
T
a,G
abp
while drawing
G
abp
.
Each of the Cases 2A-2C produces a drawing of
G
abq
such that
a, b
lies on
l
1
,l
x
+3
, respectively, and
q
lies on either
l
1
or
l
x
+3
. Hence we can extend these
drawings to draw
G
as in Case 1.
4.2 Drawing Algorithm
Decomposition.
Let
G
be an
n
-vertex plane 3-tree with the outer vertices
a,b,c
and the representative vertex
p
. A tree spanning the inner vertices of
G
is
called the
representative tree T
if it satisfies the following conditions [14]:
(a) If
n
=3,then
T
is empty.
(b) If
n
=4,then
T
consists of a single vertex.
(c) If
n>
4, then the root
p
of
T
is the representative vertex of
G
and the
subtrees rooted at the three clockwise ordered children
p
1
,
p
2
and
p
3
of
p
in
T
are the representative trees of
G
abp
,
G
bcp
and
G
cap
, respectively.
Recall that every
n
-vertex tree
T
has a vertex
v
such that the connected com-
ponentsof
T
\
v
are all of size at most
n/
2 [12]. Such a vertex
v
in
T
corresponds to
a decomposition of
G
into four smaller plane 3-trees
G
1
,G
2
,G
3
,and
G
4
, as follows.
- The plane 3-tree
G
i
,where1
3, is determined by the representative tree
rooted at the
i
th child of
v
, and thus contains at most (
n
+3)
/
2 vertices.
- The plane 3-tree
G
4
is obtained by deleting
v
and the vertices from
G
that are
descendent of
v
in
T
, and contains at most (
n
+3)
/
2 vertices.
≤
i
≤
Drawing Technique.
Without loss generality assume that
G
3
≤
G
1
.If
G
1
is incident to the outer face of
G
,thenlet(
a, b
) be the corresponding outer
edge. Otherwise,
G
1
does not have any edge incident to the outer face of
G
.Inthis
case there exists an inner face
f
in
G
that is incident to
G
1
, but does not belong
to
G
1
.Wechoose
f
as the outer face of
G
, and now we have an edge (
a, b
)of
G
1
that is incident to the outer face. Let
P
=(
w
1
,...,w
k
(=
p
)
,w
k
+1
(=
q
)
,...,w
t
)
be the maximal path in
G
such that each vertex on
P
is adjacent to both
a
and
b
,
where
G
2
≤
are the outer vertices of
G
1
,G
2
,G
3
, respectively.
Assume that
n
=
n
+3and
x
=4
n
/
9. We draw
G
on
L
x
+4
by distinguishing
two cases depending on whether
G
4
>x
or not.
Case 1 (
G
4
>x
).
Observe that
G
2
≤
{
a,b,p
}
,
{
a,p,q
}
,
{
b,q,p
}
G
1
≤
n
/
2 and since
G
3
+
G
2
+
G
1
≤
n
+5
−
G
4
,wehave
G
3
≤
5
n
/
27 + 5
/
3
≤
n
/
3 for suciently large values of
n
.
