Information Technology Reference
In-Depth Information
−
y
. Since any vector
−−−−ₒ
between
x
and
−
y
,
the angle between
A
and these edges is at most
ˀ/
2. Because the angle between
A
and
any edge on the path from
a
to
b
is at most
ˀ/
2, the path is monotone with respect to
A
.
Analogously, it can be shown that the path is monotone with respect to
B
. Recall
that
b
lies above
A
and below
B
. So the vector
ab
lies between
A
and
B
. Following
Lemma 6, the path is monotone with respect to
ab
and thusstrongly monotone.
b
j−
1
,b
j
, 1
≤
j
≤
m
also lies between
x
and
Lemmas 5 and 7 immediately imply the following.
Theorem 2.
Any proper binary tree rooted inadummy vertex has a stronglymonotone
and strictly convex drawing.
Next, we (partially) extend this result to arbitrary trees.
Theorem 3.
Any tree has a stronglymonotonedrawing.
Proof.
Let
T
be a tree. If
T
has a vertex of degree 2, we root
T
in this vertex. Otherwise,
we subdivide any edge by creating avertexofdegree 2, which we pick as root. Then,
we add a leaf to every vertex of degree 2, except the root. Now, let
v
be a vertex with
out-degree
k>
2.Let(
v,w
1
)
,...,
(
v,w
k
) be the outgoing edges of
v
ordered from
right to left. We substitute
v
by a path
,where
v
i
+1
is the left child
of
v
i
,for
i
=1
,...,k
. Then, we substitute the edges (
v,w
i
) by (
v
i
,w
i
)
,i
=2
,...,k
;
see Fig.6.
Let
T
be the resulting proper binary tree. Clearly, all vertices of
T
, except its root,
have degree 1 or 3, so
T
is a proper binary tree. We use Theorem 2 to get a strongly
monotone drawing
ʓ
T
of
T
. Then, we remove the dummy vertices inserted above and
draw the edges that have been subdivided by a path as a straight-line. This yields a
drawing
ʓ
T
of
T
that is crossing-free since the only new edges form a set of stars that
are drawn in disjoint areas of the drawing.
Now, we show that
ʓ
T
is strongly monotone. Let (
v,w
) be an edgein
T
.Let
p
=
v
=
v
1
,...,v
k
+1
be the path in
T
between
v
and
w
.Suppose
p
is monotone
with respect to some direction
d
.Thus,
v
=
v
1
,...,v
m
=
w
∠
{
−−−ₒ
v
i
v
i
+1
,
d
}
<ˀ/
2 for 1
≤
i
≤
m
−
1.
Clearly,
−
vw
=
m−
1
i
=1
−−−ₒ
v
i
v
i
+1
is a positive linear combination of
−−−ₒ
v
i
v
i
+1
,i
=1
,...,m
∠
{
−
vw,
d
}
<ˀ/
2. It follows that the path between two vertices
a
and
b
is
monotone to a direction
d
in
ʓ
T
if the path between
a
and
b
is monotone to
d
in
ʓ
T
.
With
d
=
ab
, it follows that
ʓ
T
is strongly monotone.
and hence
We add to this another positive result concerning biconnected outerplanar graphs.
Theorem 4.
Any biconnected outerplanar graphhas a stronglymonotone and strictly
convex drawing.
Proof.
Let
G
be a biconnected outerplanar graph with outer cycle
.We
place the vertices
v
2
,...,v
n−
1
in counterclockwise order on a quarter circle
C
that
has
v
1
=(0
,
0) and
v
n
=(1
,
1) as its endpoints; see Fig. 7. Since the outer cy-
cle is drawn strictly convex, the drawing is planar and strictly convex. Clearly, the
path
v
1
,...,v
n
,v
1
is
x
-and
y
-monotone. Also, every vector
−−ₒ
v
i
v
j
,j>i
lies between
x
=
(0
,
1) and
y
=(1
,
0).Thus, by Lemma 6, the drawing is strongly monotone.
v
1
,...,v
n
