Information Technology Reference
In-Depth Information
Consider vertices
s
,
t
of
G
.If
s
and
t
are contained in the same subgraph
G
i
,an
increasing-chord
st
-path in
G
i
exists by induction. If
s
is in
G
i
and
t
is
v
0
,let
ˁ
i
be the
sv
i
-path in
G
i
that uses only downward edges. By Lemma 1, path
ˁ
i
is increasing-chord
and remains so after adding edge
v
i
v
0
.
Finally, assume
t
is in
G
j
with
j
=
i
.Let
ˁ
j
be the
tv
j
-path in
G
j
that uses only
downward edges. Due to the choice of
ʵ
,
h
i
∩
h
i
ↆ
front(
ˁ
i
) contains
v
1
,...,v
k
in its
interior. Consider the path
ˁ
=(
v
i
,v
i
+1
,...,v
j
). It is self-approaching by Lemma 1;
also,
ˁ
ↆ
front(
ˁ
). It also holds
ˁ
j
ↆ
♦
j
ↆ
front(
ˁ
i
). Fact 2 lets
us concatenate
ˁ
i
,
ˁ
and
ˁ
−
j
to a self-approaching path. By a symmetric argument, it
is also self-approaching in the opposite direction and, thus, is increasing-chord.
front(
ˁ
i
) and
ˁ
j
ↆ
Since every triangulation has a spanning downward-triangulated binary cactus[5],
this implies that planar triangulations admit increasing-chord drawings.
Corollary 1.
Every planartriangulationadmits an increasing-chord drawing.
3.2
Non-triangulated Cactuses
The above construction fails if the blocks are not triangular fans since we now cannot
just use downward edges to reach the common ancestor block. Consider the family of
rooted binary cactuses
G
n
=(
V
n
,E
n
) defined as follows. Graph
G
0
is a single 4-cycle,
where an arbitrary vertex is designated as the root. For
n
≥
1, consider two disjoint
copies of
G
n−
1
with roots
a
0
and
c
0
. We create
G
n
by adding new vertices
r
0
and
b
0
both adjacent to
a
0
and
c
0
;seeFig. 3a. For the new block
ʽ
containing
r
0
,a
0
,b
0
,c
0
,
we set
r
(
ʽ
)=
r
0
. We select
r
0
as the root of
G
n
and
ʽ
as its root block. For a block
μ
i
with root
r
i
,let
a
i
,b
i
,c
i
be its remaining vertices, such that
b
i
r
i
/
E
n
.Foragiven
drawing,due to the symmetry of
G
n
, we can rename the vertices
a
i
and
c
i
such that
∠
ccw
(
# »
∈
r
i
c
i
,
# »
180
ⓦ
. We now prove the following negative result.
r
i
a
i
)
≤
Theorem 2.
Fo r
n
9
,
G
n
has no self-approaching drawing.
The outline of the proof is as follows. We show that every self-approaching draw-
ing
ʓ
of
G
9
contains a self-approaching drawing of
G
3
with the following properties.
1. If
μ
i
is contained in the subcactus rooted at
c
j
, each self-approaching
b
i
a
j
-path uses
edge
b
i
a
i
, and analogously for the symmetric case; see Lemma 5.
2. Each block is drawn significantly smaller than its parent block; see Lemma 6(i).
3. If the descendants of block
μ
form subcactuses
G
k
with
k
≥
≥
2 on both sides, the
parent block of
μ
must be drawn smaller than
μ
; see Lemma 6(ii).
Obviously, the second and third conditions are contradictory. The following lemmas
will be used to show that the drawings of certain blocks must be relatively thin, i.e., their
downward edges have similar directions; see the full version for the omitted proofs [15].
Lemma 2.
Fo r cactus
G
=(
V,E
)
and
s, t ∈ V
,consider cutvertices
v
1
, ...,
v
k
lying
on any
st
-path in
G
in this order. Then,thepath
(
s, v
1
,...,v
k
,t
)
is drawn greedily, i.e.,
each of its subpathsisgreedy.In particular,
ray(
v
1
,s
)
and
ray(
v
k
,t
)
diverge.
Obviously, this divergence property also holds for a self-approaching drawing of
any cactus. From now on, we consider a fixed self-approaching drawing
ʓ
of
G
9
.For
