Information Technology Reference
In-Depth Information
use 2
k
integral vectors having, by Lemma 1, an angular resolution of
ʩ
(1
/k
),wediffer
from the best possible angular resolution 2
ˀ/k
only by a constant factor.
4
Strongly Monotone Drawings
We first show how to draw any proper binary tree (that is, any internal vertex has exactly
two children). We name ourstrategythe
disk-algorithm
. Then, we generalize ourresult
to arbitrary trees. Further, we show that connected planar graphs do not necessarily have
astrongly monotone drawing. Finally, we show how to draw biconnected outerplanar
graphs in a strongly monotone fashion.
Let
T
be a proper binary tree, let
D
be any disk with center
c
,andlet
C
be the
boundary of
D
. Recall that a strictly convex drawing cannot have a vertex of degree 2.
Thus, we consider the root of
T
adummy vertex and ensure that the angle at the root
is
ˀ
.Wedraw
T
inside
D
. We start by mapping the root of
T
to
c
. Then, we draw a
horizontal line
h
through
c
and place the children of the root on
h
int(
D
) such that
they lie on opposite sites relative to
c
.Wecut off two circular segments by dissecting
D
with two vertical lines running through points representing the children of the root.
We i n ductively draw the right subtree of
T
into the right circular segment and the left
subtree into the left circular segment.
In any step of the inductive process, we are given a vertex
v
of
T
, its position in
D
(which we also denote by
v
)andacircular segment
D
v
;seeFig. 4a. The preconditions
for our construction are that
(i)
v
lies in the relative interior of the chord
s
v
that delimits
D
v
,and
(ii)
D
v
is empty, that is, the interiors of
D
v
and
D
u
are disjoint for any vertex
u
that
does not lie on a root-leaf path through
v
.
In order to place the two children
l
and
r
of
v
(if any), we shoot a ray
v
from
v
per-
pendicular to
s
v
into
D
v
.Let
v
be the point where
v
hits
C
. Consider the chords that
connect the endpoints of
s
v
to
v
. The chords and
s
v
form a triangle with height
vv
.
The height is contained in the interior of the triangle and splits it into two right sub-
triangles. The chords are the hypotenuses of the subtriangles. We contruct
l
and
r
by
connecting
v
to these chords perpendicularly. Note that, since the subtriangles are right
triangles, the heights lie inside the subtriangles. Hence,
l
and
r
lie in the relative interi-
ors of the chords. Further, note that the circular segments
D
l
and
D
r
delimited by the
two chords are disjoint and both are contained in
D
v
. Hence,
D
l
and
D
r
are empty, and
the preconditions for applying the above inductive process to
r
and
l
with
D
l
and
D
r
are fulfilled. See Fig.4bfortheoutputofouralgorithm for a tree of height 3.
∩
Lemma 5.
Fo r a proper binary tree rooted inadummy vertex, thedisk-algorithm yields
a strictly convex drawing.
Proof.
Let
T
be a proper binary tree and let
f
beafaceofthedrawinggenerated by the
algorithm described above. Clearly,
f
is unbounded. Let
a
and
b
be the leaves of
T
that
are incident to the two unbounded edges of
f
,andlet
v
be the lowest common ancestor
of
a
and
b
;seeFig. 4b. Consider the two paths from
v
to
a
and
b
.Weassume that the
path from
v
through its left child ends in
a
and the path through its right child ends in
b
.
