Information Technology Reference
In-Depth Information
ˁ
b
2
r
t
t
120
ⓦ
u
u
ˁ
r
s
g
s
b
(a)
(b)
(c)
(d)
(e)
Fig. 5.
(a)-(c) 30
ⓦ
-Schnyder drawings are increasing-chord; (d),(e) special case of planar 3-trees.
the pattern from Fig.5aat
v
. For the induction step, consider a triangular face
xyz
and assume that the pattern is centered at one of its vertices, say
x
,such that the other
two vertices are in the interiors of two distinct cones; see Fig. 5d. It is now possible
to move the pattern inside the triangle slightly, such that the same holds for all three
vertices
x, y, z
;seeFig. 5e. We insert the new vertex at the center of the pattern and
again get the situationasinFig.5d.
Lemmas 8 and 9 provide a constructive proof for the following theorem.
Theorem 3.
Every planar3-treehas a planarincreasing-chord drawing.
5
Self-Approaching Drawings in the Hyperbolic Plane
2
.
Kleinberg [12] showed that any tree can be drawn greedily in the hyperbolic plane
H
2
in this regard. Since self-
approaching drawings are closely related to greedy drawings, it is natural to investigate
the existence of self-approaching drawingsin
2
.Thus,
2
is more powerfulthan
This is not the case in
R
H
R
2
.
H
2
,inwhich
2
is represented by the unit
We s h a l l use the
Poincar´edisk
model for
H
H
2
:
disk
D
=
and lines are represented by circular arcs orthogonal
to the boundary of
D
. For an introduction to the Poincare disk model, see e.g. Klein-
berg [12] and the references therein.
First, let us consider a tree
T
=(
V,E
).Adrawing of
T
in
{
x
∈
R
|
x
|
<
1
}
2
is self-approaching if
and only if no normal on an edgeof
T
in any point crosses another edge[1].Thesame
condition holds in
R
2
;seefull version for the proof [15]. According to the characteriza-
tion by Alamdari et al. [1], some binary trees have no self-approaching drawingsin
H
2
.
R
2
.
We show that this is no longer the case in
H
Theorem 4.
Let
T
=(
V,E
)
be a tree, such thateachnode of
T
hasdegree either 1
or 3. Then,
T
has a self-approaching drawing in
2
,inwhich everyarc hasthesame
hyperbolic lengthandevery pair of incident arcs forms an angle of
120
ⓦ
.
H
Proof.
For convenience, we subdivide each edgeof
T
once. We shall show that both
pieces are collinear in the resulting drawing
ʓ
and have the same hyperbolic length.
First, consider a regular hexagon
=
p
0
p
1
p
2
p
3
p
4
p
5
centered at the origin
o
of
D
;
2
, it can have angles smaller than 120
ⓦ
. We choose them to be 90
ⓦ
(any
angle between 0
ⓦ
and 90
ⓦ
would work). Next, we draw a
K
1
,
3
with center
v
0
in
o
and
the leaves
v
1
,v
2
,v
3
in the middle of the arcs
p
0
p
1
,
p
2
p
3
,
p
4
p
5
respectively.
see Fig.6a.In
H
