Information Technology Reference
In-Depth Information
ˁ
i
ˁ
−
1
j
s
t
v
i
v
j
v
1
v
k
ʵ
4
k
ʳ
i
s
i−
1
v
i
v
i
v
j
ʲ
v
1
ʱ
v
i−
1
v
0
(a)
(b)
(c)
Fig. 2.
Drawing atriangulated binary cactus with increasing chords inductively. The draw-
ings
ʓ
i,ʵ
of the subcactuses,
ʵ
=
4
k
, are contained inside the gray cones. It is
ʲ
=90
ⓦ
− ʵ
,
ʵ
γ
=90
ⓦ
+
ʵ
/
2.
3.1
Increasing-Chord Drawings of Triangulations
We show that every downward-triangulated binary cactus has an increasing-chord draw-
ing. The construction is similar to the one of the greedy drawings of binary cactuses in
the two proofs of the Papadimitriou-Ratajczak conjecture [5, 13]. Our proof is by induc-
tion on the height of the BC-tree. We show that
G
can be drawn such that all downward
edges are almost vertical and the remaining edges almost horizontal. For vertices
s, t
,
an
st
-path with increasing chords goes downwards to some block
μ
,thensidewaysto
another cutvertex of
μ
and, finally, upwards to
t
.Let
#
e
1
,
#
e
2
be vectors (1
,
0)
, (0
,
1)
.
Theorem 1.
Let
G
=(
V,E
)
be a downward-triangulated binary cactus. For any
0
ⓦ
<
ʵ<
90
ⓦ
,there exists an increasing-chord drawing
ʓ
ʵ
of
G
,such thatforeachvertex
v
contained in someblock
μ
,
v
=
r
(
μ
)
,the angle formed by
# »
r
(
μ
)
v
and
#
e
2
is at most
2
.
Proof.
Let
G
be rooted at block
ʽ
.Asour base case, let
ʽ
=
G
beatriangular fan
with vertices
v
0
,v
1
,...,v
k
and root
v
0
=
r
(
ʽ
).Wedraw
v
0
at the origin and distribute
v
1
, ...,
v
k
on the unit circle, such that
∠
(
#
e
2
,
# »
∠
(
# »
v
0
v
i
,
# »
v
0
v
i
+1
)=
ʱ
,
ʱ
=
ʵ/k
;seeFig. 2a. By Lemma 1, path (
v
1
,...,v
k
) has increasing chords.
Now let
G
have multiple blocks. We draw the root block
ʽ
,
v
0
=
r
(
ʽ
), as in the pre-
vious case, but with
ʱ
=
v
0
v
1
)=
kʱ/
2 and
2
k
. Then, for each
i
=1
,...,k
, we choose
ʵ
=
ʵ
ʵ
4
k
and draw
the subcactus
G
i
rooted at
v
i
inductively, such that the corresponding drawing
ʓ
i,ʵ
is
v
0
v
i
instead of
#
e
2
;seeFig 2b. Note that
ʵ
is the angle of the cones (gray)
containing
ʓ
i,ʵ
.Obviously, all downward edges form angles at most
2
with
#
e
2
.
We must be able to reach any
t
in any
G
j
from any
s
in any
G
i
via an increasing-
chord path
ˁ
. To achieve this, we make sure that no normal on a downward edgeof
G
i
crosses the drawing of
G
j
,
j
# »
aligned at
=
i
.Let
ʛ
i
be the cone with apex
v
i
and angle
ʵ
aligned
# »
ʛ
i
(gray regions in Fig.2b).Let
s
i
and
s
i
be the left and right boundary
rays of
ʛ
i
with respect to
with
v
0
v
i
,
v
0
∈
# »
v
0
v
i
,and
h
i
,
h
i
the halfplanes with boundaries containing
v
i
and orthogonal to
s
i
and
s
i
respectively, such that
v
0
∈
h
i
∩
h
i
.Define
♦
i
=
ʛ
i
∩
h
i−
1
∩
h
i
+1
(thin bluequadrangle in Fig. 2c), and analogously
♦
j
for
j
=
i
. It holds
h
i
∩
h
i
for each
i
♦
j
ↆ
=
j
. We now scale each drawing
ʓ
i,ʵ
such that it is contained
l
uv
for
in
♦
i
. In particular, for any downward edge
uv
in
ʓ
i,ʵ
,wehave
ʓ
j,ʵ
ↆ
♦
j
ↆ
j
=
i
. We claim that the resulting drawing of
G
is an increasing-chord drawing.
