Information Technology Reference
In-Depth Information
respectively. Similarly,
G
bqp
admits a drawing
ʓ
bpq
on
L
x
+2
such that the
vertices
p,b,q
lie on
l
1
,l
x
+2
,l
x
+2
, respectively. By Lemma 5,
G
apq
admits
adrawing
ʓ
apq
on
L
(
n
+2)
/
3
such that
a,p,q
lie on
l
1
,l
1
,l
x
+2
, respectively.
Finally, by Stretch and Reshape we can merge these drawings to obtain a
drawing of
G
abq
on
L
x
+3
. Figures 3(f)-(g) show an illustration.
Case 1C (
leaf
(
T
q,G
bqp
)
≤ x
).
The drawing of this case is similar to Case
1B. The only difference is that we use
T
q,G
bqp
while drawing
G
bqp
.
Observe that each of the Cases 1A-1C produces a drawing of
G
abq
such that
a, b
lie on
l
1
,l
x
+3
, respectively, and
q
lies on either
l
1
or
l
x
+3
. We stretch it to a
drawing on
L
x
+4
such that
a, b
lies on
l
1
,l
x
+4
, respectively, and
q
lies on either
l
2
or
l
x
+3
.If
q
lies on
l
2
, then we draw the path
w
k
+1
,...,w
t
(=
c
) in a zigzag
fashion, placing the vertices on
l
2
and
l
x
+3
alternatively such that each vertex
is visible to both
a
and
b
. Similarly, if
q
lies on
l
x
+3
, then we place the vertices
w
k
+1
,...,w
t
(=
c
)on
l
x
+3
and
l
2
alternatively, as shown in Figure 4(a). For each
i>k
+ 1, Lemma 4 ensures that the graphs
G
aw
i
w
i−
1
and
G
bw
i
w
i−
1
are plane
3-trees. Since max
∀i>k
+1
{
G
aw
i
w
i−
1
,G
bw
i
w
i−
1
}≤
x
,wecandraw
G
aw
i
w
i−
1
and
G
bw
i
w
i−
1
using Lemma 5 inside their corresponding triangles.
Case 2 (
leaf
(
T
p,G
abp
)
>x
).
Since
G
abp
≤
n
/
2, by Lemma 1,
leaf
(
T
a,G
abp
)+
n
−
leaf
(
T
p,G
abp
)
5
n
/
9.Hencewedraw
G
abq
considering
leaf
(
T
b,G
abp
)
≤
≤
the following scenarios.
n
/
2,
by Lemma 1, one of the trees in the Schnyder realizer of
G
bqp
has at most
n
/
3
≤ x
).
Since
G
bqp
≤
Case 2A (
leaf
(
T
a,G
abp
)
≤ x
and
leaf
(
T
b,G
abp
)
x
,thenwedraw
G
abq
on
L
x
+3
,where
a,b,p,q
lie on
l
1
,l
x
+3
,l
x
+2
,l
1
, respectively, as in Figure 4(b). Otherwise,
either
leaf
(
T
b,G
bpq
)
≤
x
leaves. If
leaf
(
T
p,G
bpq
)
≤
x
.Inthiscasewedraw
G
abq
on
L
x
+3
,where
a,b,p,q
lie on
l
1
,l
x
+3
,l
2
,l
x
+3
, respectively, as in Figure 4(c).
Case 2B (
leaf
(
T
a,G
abp
)
>x
and
leaf
(
T
b,G
abp
)
≤
x
or
leaf
(
T
q,G
bpq
)
≤
≤ n
/
9).
If
leaf
(
T
p,G
bpq
)
≤
n
/
3, then we first draw
G
bpq
using Lemma 2 such that
b,p,q
lie on
l
n
/
3+2
,
l
n
/
3+2
,l
1
, respectively, and then use the Stretch condition to shift
b
to
l
x
+3
.
By Lemma 2 and the Stretch condition, there exists a drawing of
G
abp
on
L
x
+3
with
a,b,p
lying on
l
1
,l
x
+3
,l
n
/
3+2
, respectively. Since
G
apq
≤
(
n
+
2)
/
3, we can draw
G
apq
using Lemma 5 inside triangle
apq
. Figure 4(d)
illustrates the scenario after applying Stretch and Reshape.
If
leaf
(
T
p,G
bpq
)
>n
/
3, then by Lemma 1 either
leaf
(
T
b,G
bpq
)
n
/
3or
≤
n
/
3. Hence we can use Lemma 2 and the Stretch condition
leaf
(
T
q,G
bpq
)
≤
b
p
b
q
l
x
+4
b
q
l
x
+3
b
b
l
x
+3
l
x
+3
q
l
n
/
3+2
w
k
+2
p
p
w
k
+1
l
n
/
9
p
l
1
l
1
a
l
1
l
1
a
a
a
q
q
a
(a)
(c)
(d)
(e)
(b)
Fig. 4.
(a) Illustrating Case 1. (b)-(c) Illustrating Case 2A. (d)-(e) Case 2B.
