Information Technology Reference
In-Depth Information
Stretch.
For any integer
t
k
,
G
admits a drawing
ʓ
on
L
t
such that
a,b,c
lie on
l
1
,l
t
,l
i
, respectively (e.g., Figure 3(c)).
≥
For any triangulation
H
with the outer vertices
a,b,c
,let
T
a,H
,T
b,H
,T
c,H
be the Schnyder trees rooted at
a,b,c
, respectively. By
leaf
(
T
)wedenotethe
number of leaves in
T
. The following lemma establishes a sucient condition for
aplane3-tree
G
to have a straight-line drawing with height at most 4(
n
+3)
/
9+4.
Lemma 6.
Let G be an n-vertex plane
3
-tree with outer vertices a,b,c in
clockwise order. Let w
1
,...,w
k
(=
p
)
,w
k
+1
(=
q
)
,...,w
t
(=
c
)
be the maximal
path P such that each vertex on P is adjacent to both a and b. Assume that
n
=
n
+3
,andx
=4
n
/
9
.IfG
apq
≤
(
n
+2)
/
3
, G
bpq
≤
G
abp
≤
n
/
2
and
G
aw
i
w
i−
1
,G
bw
i
w
i−
1
}≤
4
n
/
9
,thenG admits a drawing with height
max
∀i>k
+1
{
at most
4
n
/
9+4
.
Proof.
Let
H
be the subgraph of
G
induced by the vertices
.
The idea of the proof is first to construct a drawing of
H
on
L
x
+4
, and then to
extend it to the required drawing using Lemmas 2-5. We distinguish two cases
depending on whether
leaf
(
T
p,G
abp
)
{
a, b
}∪{
w
k
,...,w
t
}
≤
x
or not.
Case 1 (
leaf
(
T
p,G
abp
)
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
≤
≤
x
leaves. We now draw
G
abq
considering the following scenarios.
Case 1A(
leaf
(
T
p,G
bqp
)
≤ x
).
By Lemma 2and the Stretch condition,
G
abp
ad-
mits a drawing
ʓ
abp
on
L
x
+2
such that the vertices
a,b,p
lie on
l
1
,l
x
+2
,l
x
+2
,re-
spectively. Similarly,
G
bqp
admitsadrawing
ʓ
bpq
on
L
x
+2
such thatthe vertices
q,b,p
lie on
l
1
,l
x
+2
,l
x
+2
, respectively, as shown in Figure 3(d). By the Stretch
property,
ʓ
abp
can be extended to a drawing
ʓ
abp
on
L
x
+3
,where
a,b,p
lie on
l
1
,l
x
+3
,l
x
+2
, respectively. Similarly,
ʓ
bqp
can be extended to a drawing
ʓ
bqp
on
L
x
+3
,where
q,b,p
lie on
l
1
,l
x
+3
,l
x
+2
, respectively. Since
G
apq
≤
(
n
+2)
/
3,by
Lemma 5 and the Stretch condition,
G
apq
admits a drawing
ʓ
apq
on
L
(
n
+2)
/
3
.
Finally, by the Stretch property
ʓ
apq
can be extended to a drawing
ʓ
apq
on
L
x
+2
such that
a,p,q
lie on
l
1
,l
x
+2
,l
1
, respectively, and by the Reshape prop-
erty we can merge these drawings to obtain a drawing of
G
abq
on
L
x
+3
. Fig-
ure 3(e) depicts an illustration.
Case 1B (
leaf
(
T
b,G
bqp
)
≤ x
).
By Lemma 2 and the Stretch condition,
G
abp
admits a drawing
ʓ
abp
on
L
x
+2
such that the vertices
a,b,p
lie on
l
1
,l
x
+2
,l
1
,
b
l
t
b
q
b
p
p
b
p
b
b
q
b
b
l
k
l
x
+2
l
x
+2
l
k
p
p
q
e
e
r
l
i
l
1
l
i
l
1
l
i
l
1
d
c
l
i
l
1
d
c
p
q
a
q
a
q
a
a
a
a
q
p
a p
a
p
(a)
(b)
(c)
(e)
(f)
(g)
(d)
Fig. 3.
(a)-(b) Illustrating Reshape. (c) Illustrating Stretch. (d)-(e) Illustration for
Case 1A. (d)-(e) Illustration for Case 1B.
