Information Technology Reference
In-Depth Information
3
3
2
9
13
1
1
2
4
4
6
5
7
1
4
8
11
14 15
15
8
13
14
3
6
9
10 12
11
12
10
57
(a) tree with edgenumbers
s
(
·
)
(b) grid drawing of the tree
Fig. 2.
A strictly convex drawing of a tree
The drawing is then generated by translating the selected primitive vectors. In the fol-
lowing,an
extended
subtree will refer to a subtree including the edge leading into the
subtree (if the subtree is not the whole tree).
Every edge
e
will be assign with a number
s
(
e
).Thisnumber will refer to the rank of
the edge's slope (in circular order) in the final assignment. The rank assignment is done
in a recursive fashion. At any time, let
s
be 1 plus the maximumrank
s
(
e
) assigned
so far. Initially,
s
=1.Let
e
=
uv
be an edge (directed away from the root), and
let
v
1
,v
2
,...,v
be the children of
v
ordered from left to right. We recursively set the
ranks of all edges in the extended subtree rooted at
v
1
.Thenweset
s
(
e
)=
s
(which
increases
s
by one). Finally, we set, for
i
=2
,...,
, the ranks of the edges in the
extended subtree rooted at
v
i
. For an example of a tree with its edge ranks, see Fig.2a.
Second, we assign actual slopes to the edges. Let
e
be an edge with
s
(
e
)=
j
.Then
we assignto
e
some vector
s
j
∈
Z
2
and draw
e
as a translate of
s
j
.Wepickthe
vectors
s
1
,s
2
,...,s
n−
1
by selecting asufficiently large set of primitive vectors and
their reflections in counterclockwise order, see Section 2. Ourdrawing algorithm has
the following requirements, which can be fulfilled as the following lemma shows:
(R1) Edges that are incident to the root and consecutive in circular order are assigned
to vectors that together span an angle less than
ˀ
.
(R2) In every extended subtree hanging off the root, the edges are assignedtoasetof
vectors that spans an angle less than
ˀ
.
Lemma 3.
We can select
n
−
1
vectors with distinct directed slopes froma
[
−
d, d
]
×
√
n
[
−
d, d
]
grid with
d
=4
such thattherequirements (R1) and(R2)are fulfilled.
Proof.
We first preprocess our tree by adding temporary edges at some leaves. These
edges will receive slopes, but are immediately discarded after the assignment.
First, our objective is to ensure that the tree can be split up into three parts that all
have
n
edges. In particular, we adjust the sizes of the extended subtrees hanging off
the root by adding temporary edges such that we can partition them into three sets of
consecutive extended subtrees which all contain
n
edges. Note that we have to add 2
n
+
1 edges to achieve this.
