Information Technology Reference
In-Depth Information
using the red slope
r
2
=
b
2
−
ʵ
andsothat
s
ʷ
2
and
t
ʷ
2
are horizontally aligned. Finally,
we attach
ʓ
ʷ
1
and
ʓ
ʷ
2
(possibly scaling one of them). Invariants
I1.
and
I2.
hold by
construction. Also,
ʓ
μ
is contained in a triangle
˄
μ
such that
s
μ
and
t
μ
are placed at the
corners of its base. Moreover, we have that
ʔ
(
s
μ
)=
ʔ
(
s
ʷ
1
)+1, and
ʲ
μ
=
ʲ
ʷ
1
+
ʱ
<
ʔ
(
s
ʷ
1
+ 1)
ʱ
+
ʱ
=
ʔ
(
s
ʷ
1
+ 2)
ʱ
=
ʔ
(
s
μ
+ 1)
ʱ
. Similarly,
ʔ
(
t
μ
)=
ʔ
(
t
ʷ
2
)+1, and
ʳ
μ
=
. Hence, Invariant
I3.
holds. In case (
iii
) we can usethesameconstruction as in case (
ii
). Notice that the edge
(
s
μ
,
t
μ
) can be safely drawn using the horizontal blue slope
b
1
. All invariants hold.
ʳ
ʷ
2
+
ʱ
<
ʔ
(
t
ʷ
2
+ 1)
ʱ
+
ʱ
=
ʔ
(
t
ʷ
2
+ 2)
ʱ
=
ʔ
(
t
μ
+ 1)
ʱ
be an S
∗
-node differentfrom
Lemma 3.
Let
μ
ʾ
.ThenG
μ
admits a straight-linedraw-
ing
ʓ
μ
that respects Invariants
I1.
,
I2.
and
I3
.
Proof.
Refer to Figure 2(d). Denote by
ʷ
the child of
μ
that is an
S
-node with a tail
at either
s
μ
or
t
μ
.Suppose that
ʷ
has a tail at
t
μ
(the case when the tail is at
s
μ
is
symmetric). Denote by
ˈ
the child of
μ
that is a
Q
-node having
t
ˈ
=
s
ʷ
and
s
ˈ
=
s
μ
as poles. Finally denote by
ʷ
1
,
ʷ
2
,...,
ʷ
k
the remaining children of
μ
. Recall that
s
ʷ
1
=
s
ʷ
i
=
s
ʷ
k
and that
t
ʷ
1
=
t
ʷ
i
=
t
ʷ
k
.If
k
= 1, we first rotate
ʓ
ʷ
1
so that the segment
s
ʷ
1
t
ʷ
1
uses the blue slope
b
2ʔ
.If
k
>
1, we combine the drawings
ʓ
ʷ
k
with the
same technique described for
P
-nodes (recall that indeed they were children of a
P
-
node before the creation of the
S
∗
-node), and, again, we rotate the resulting drawing so
that the base of its bounding triangle uses the blue slope
b
2ʔ
. Then we attach
ʓ
ʷ
1
,
ʓ
ʷ
2
,...,
ʓ
ʷ
to
ʓ
ʷ
1
(after
ʓ
ʷ
has been horizontally flipped). Also, we scale
ʓ
ʷ
so that its tail can be redrawn
by using the red slope
r
2ʔ
and such that
t
ʷ
=
t
μ
coincides with
t
ʷ
1
=
t
ʷ
k
. Finally, we
redraw the edge associated with
, starting from the point representing
t
ˈ
=
s
ʷ
, using
the red slope
r
2
and stretch it enoughthat
s
ˈ
=
s
μ
and
t
μ
are horizontally aligned.
See also Figure 2(d) for an illustration. Invariants
I1.
and
I2.
hold by construction.
Consider now Invariant
I3.
. By construction
ˈ
˄
μ
such that
s
μ
and
t
μ
are placed at the corners of its base. For the sake of description, in what
follow we still denote by
ʓ
μ
is contained in a triangle
ʓ
ʷ
the drawing of
G
ʷ
minus the tail of
ʷ
(i.e., minusan
edge), and as
ʓ
ʷ
. To prove the second part of Invariant
I3.
,weshould prove that the line
passing through
s
μ
˄
ʷ
the surrounding triangle of
with slope
b
3
= 2
ʱ
does not
cross the drawing of
ʓ
ʷ
, i.e., is such that
ʓ
ʷ
is placed in the half-plane
H
defined
by
and containing the segment
s
μ
t
μ
. Denote by
ʴ
x
the horizontal distance between
the point where
s
μ
is drawn and the leftmost endpoint of
˄
ʷ
. Also, denote by
h
ʷ
the
height of
˄
ʷ
.Our condition is satisfied if the following inequality holds tan(2
ʱ
)
ʴ
x
≥
tan(
ʱ
)
ʴ
x
+
h
ʷ
.Let
w
ʷ
be the length of the base of
˄
ʷ
, in the worst case (the case that
maximizes
h
ʷ
), we have that
h
ʷ
=
w
2
1
tan(
)
, which means that the degree of the two
ʱ
vertices placed as endpoints of the base of
˄
ʷ
is
ʔ
. Moreover, it is possible to see that
w
ʷ
=
tan(ʱ)ʴ
x
−
tan(ʱ
−
ʵ)ʴ
x
tan(ʱ
−
ʵ)
.Substituting
w
ʷ
in
h
ʷ
and
h
ʷ
in the above inequality we have:
)+
tan(ʱ)
−
tan(ʱ
−
ʵ)
tan(2
ʱ
)
≥
tan(
ʱ
2tan(ʱ
−
ʵ)tan(ʱ)
. With some manipulation we get: tan(
ʱ
−
ʵ
)
≥
)
2tan(2ʱ)tan(ʱ)
−
2tan(ʱ)tan(ʱ)+1
. Now, since the tangent function is strictly increasing in
(
tan(
ʱ
arctan
2tan(ʱ)tan(ʱ)+1
. Since the valueof
tan(
ʱ
)
−
2
,
2
),wehave:
ʵ
≤
ʱ
−
ʱ)tan(ʱ)
−
2tan(2
ʵ
has been chosen equal to the right-hand side of the above inequality, the inequality
holds. Hence,
ʲ
μ
<
2
ʱ
=(
ʔ
(
s
μ
)+1)
ʱ
(since
ʔ
(
s
μ
)=1). With a symmetric argument
