Information Technology Reference
In-Depth Information
We will useaslightly stronger version of Lemma 4 in which
G
is allowed to be a
mulitgraph. Pach and Wenger's proof of Lemma 4 works for this case.
For part (
ii
) Pach and Wenger show that a Hamiltonian cycle can be drawn at fixed
vertex locations
ʵ
-close to a star connecting all the vertices. For our application, we
replace their star with a straight-line drawing of a tree
T
whose leaves are the vertices
v
i
.
Independently of ourresult, the generalization of part (
ii
) to trees has essentially been
shown by Chan et al. [6]. Since their goal was the minimization of the edgelengths,
they did not giveanestimateonthenumber of bends. We now show how to draw the
Hamiltonian cycle. We will later show how to draw the remaining edges.
Lemma 5.
Let
C
be a cycle with fixed vertex locations, andsuppose we are givena
straight-lineplanardrawing of a tree
T
,inwhich the vertices of
C
are leaves of
T
at
their fixed locations. Then for every
ʵ>
0
there is a planar poly-linedrawing of
C
with
at most
2
|
E
(
T
)
|−
1
bends per edge and
ʵ
-close to
T
.
Proof.
Let
p
1
,...,p
n
be the vertices of
C
in their order along the cycle. We build a
planar poly-line drawing of
C
as follows. Let
ʘ
i
be an
iʵ/n
-approximation of
T
for
1
i<n
(which we can construct using Lemma 2). We start at
p
1
.Suppose we have
already built the poly-line drawing of
p
1
,...,p
i
and we want to add
p
i
p
i
+1
.Let
Q
i
be
the uniquepathin
T
connecting
p
i
to
p
i
+1
. Create
ʘ
i
from
ʘ
i
by keeping only the
≤
vertices of
ʘ
i
close to (approximating) vertices in
T
i
:=
j≤i
Q
j
. This removes parts
of the walk along
ʘ
i
which we patch up as follows: suppose
v
is an interior vertex of
T
i
,and
v
is incident to
e
which does not lie on
T
i
.Then
v
is approximated by two
vertices
v
1
and
v
2
which lie on bisectors formed by
e
with neighboring edges. Now
v
1
and
v
2
belong to
ʘ
i
,but the path along
ʘ
i
between them got removed (since
e
does
not belong to
T
i
). We add
v
1
v
2
to
ʘ
i
to connect them. Note that
v
1
v
2
does not pass
through
v
since
v
is incident to at least three edges (
e
and two edges of
T
i
), and it does
not cross any edges of any
ʘ
j
with
j<i
,since
T
i
is monotone: if
e
∈
E
(
ʘ
i
),then
e
E
(
ʘ
j
) for
j<i
.SeeFigure 3 for an illustration. Now both
p
i
and
p
i
+1
correspond
to unique vertices on
ʘ
i
(since they are leaves), so we can pick a facial walk
v
1
,...,v
k
on
ʘ
i
which connects
p
i
to
p
i
+1
and which avoids passing by
p
1
. We now add line
segments
p
i
v
2
,
v
2
v
3
,
...
,
v
k−
2
v
k−
1
,
v
k−
1
p
i
+1
to the poly-line drawing of
C
. We treat
the final edge
p
n
p
1
similarly, except that we move along
ʘ
n−
1
back to
p
1
in the last
step, which we can do, since none of the intermediate paths passed by
p
1
. Each edgeof
C
is replaced by a polygonal arc with at most 2
∈
|
E
(
T
)
|−
1 bends.
As mentioned earlier, the following lemma is close to a result by Chan et al. [6],
except for the claim aboutthenumber of bends, and the rotation system (which we
require for our main result).
Lemma 6.
Let
G
be a Hamiltonian multi-graphwithagiven planarembedding and
fixed vertex locations. Suppose we are givenastraight-linedrawing of a tree
T
whose
leaves include all the vertices of
G
attheir fixed locations. Then for every
ʵ>
0
there
is a planar poly-linedrawing of
G
thatis
ʵ
-close to
T
,thatrealizes the given embed-
ding, where the vertices of
G
are attheir fixed locations, where each edge has at most
4
|
E
(
T
)
|−
1
bends, and where each edgecomes close to any leafof
T
at most twice.
