Information Technology Reference
In-Depth Information
Ourcontribution.
We present two main results. First, we show that any
n
-vertex tree
admits a strictly convex and, hence, monotone drawing on the
O
(
n
1
.
5
)
O
(
n
1
.
5
) grid
(see Section 3). As the drawingsofAngelini et al. [2], ourdrawings are slope-disjoint,
butweuse a different set of primitive vectors (based on Farey sequences), which slightly
decreases the grid size. (This also works for the BFS-based algorithm of Angelini et al.)
Instead of pre-oder, we use a kind of in-oder traversal (first child - root - other children)
of the input tree, which helps us to achieve convexity. Our ideas can be applied to
modify the optimal angular resolution algorithm of Carlson and Eppstein [6] such that
adrawing on an
O
(
n
1
.
5
)
×
O
(
n
1
.
5
) grid is constructed at the expense of missing the
optimal angular resolution by a constant factor. Second, we show that any tree admits a
strongly
monotone drawing (see Section 4). So far, no positive results have been known
for strongly monotone drawings.
In the case of proper binary trees, ourdrawings are additionally strictly convex. For
biconnected outerplanar graphs, it is easy to construct strongly monotone drawings.
On the other hand, we present a simply-connected planar graph that does not have a
strongly monotone drawing in any embedding.
We leave it as an open question whether trees admit strongly monotone drawingson
a grid of polynomial size (see Section 5).
×
2
Building Blocks: Primitive Vectors
The following algorithms require a set of integral vectors with distinct directed slopes
and bounded length. In particular, we ask for a set of
primitive vectors
P
d
=
{
(
x, y
)
|
gcd(
x, y
)
.Our goal is to find the right valueof
d
such that
P
d
contains at least
k
primitive vectors, where
k
is a number that we determine later.
We can then use the reflections on the lines
x
=
y
,
y
=0and
x
=0to get a sufficiently
large set of integer vectors with distinct directed slopes. The edges of the monotone
drawings in Section 3 are translates of these vectors; each edge uses a different vector.
∈{
1
,d
}
,
0
≤
x
≤
y
≤
d
}
Assume that we have fixed
d
and want to gener-
ate the set
P
d
. If we consider each entry (
x, y
) of
P
d
to be a rational number
x/y
and order these numbers
by value, we get the
Farey sequence
F
d
(see, for ex-
ample, Hardy and Wright's topic [8]). The Farey se-
quence is well understood. In particular, it is known
that
=3
d
2
/ˀ
2
+
O
(
d
log
d
) [8, Thm. 331].
Furthermore, the entries of
|F
d
|
F
d
can be computed in
). We remark that the set
d
F
d
coin-
cides with the entries of the Stern-Brocot tree. How-
ever, collecting the latter level by level is not the most
effective method to build a set of primitive vectors for
ourpurpose.
To get access to a set of
k
primitive vectors, we use
the first
k
entries of the Farey sequence
time
O
(
|F
d
|
Fig. 1.
The 13 primitive vectors ob-
tained from
F
6
. The smallest angle
of
≈
1
.
14
ⓦ
is realized between the
vectors (4
,
5) and (5
,
6) marked
with white dots; the best possible
angular resolution in this case is
45
ⓦ
/
12 = 3
.
75
ⓦ
.
F
d
,for
d
:=
√
k
4
, replacing each rational by its corresponding
2d vector. By selecting
k
vectors form this set we get
a set of exactly
k
primitive vectors, which we denote by
V
k
;seeFig.1.
