Information Technology Reference
In-Depth Information
3
5
1
2
4
Fig. 3.
The underlying tree
T
is in black (thick edges), angle bisectors in gray; the
ʘ
i
are drawn
as thin black edges; to reduce clutter, we are not showing the remaining edges of
ʘ
i
; the drawing
of
C
is indicated by the green line.
The obvious idea—routing edges along the Hamiltonian cycle
C
—only gives a
quadratic bound on the number of bends, since each edgewould follow the path of
a linear number of edges of
C
, and each edgeof
C
has a linear number of bends. Pach
and Wenger came up with an ingenious way to construct auxiliary curves with few
bends based on the level curves
ʘ
i
which carry the cycle
C
in the proof of Lemma 5.
Proof.
Let
C
be the Hamiltonian cycle of
G
and let
G
1
and
G
2
be the two outerplanar
graphs composed of
C
and, respectively, of the edges of
G
outside and inside
C
.Using
Lemma 5 we find a planar poly-line drawing of
C
on
V
(
G
). We need to show how to
draw
G
1
and
G
2
respecting the planar embeddingsinduced by the given embedding
of
G
.Let
n
=
|
V
(
G
)
|
and
m
i
=
|
E
(
G
i
)
|
. We only describe how to draw
G
1
,since
G
2
can be handled analogously. Let
Δ
i,k
, 1
m
1
be a
kʵ/
(
nm
1
)-approximation
of
ʘ
i
constructed using Lemma 2. For a fixed
i
, each
Δ
i,k
crosses
C
twice: when
C
moves from
p
i
to
ʘ
i
+1
, and when it finally moves back from
ʘ
n
to
p
1
.AsinPach and
We nger, we can then split
Δ
i,k
at the crossings and connect their free ends to
p
1
and
p
i
,
resulting (for each
k
)intwocurves
Δ
i,k
and
Δ
i,k
connecting
p
1
to
p
i
,where
Δ
i,k
lies
outside
C
(these are the curves we use for
G
1
)and
Δ
i,k
inside
C
(these are the curves
we use for
G
2
). Each such curve has at most 2
≤
k
≤
|
E
(
T
)
|−
1 bends. As in the proof of
E
(
G
1
) by concatenating
Δ
i,k
with
Δ
j,k
.
Since we chose
m
1
such approximations, we can do this for each edgein
G
1
.Thereare
two problems remaining:edges
p
i
p
j
now all pass through
p
1
andtheycould potentially
cross (rather than just touch) there. Pach and Wenger show that any two edges touch,
so the drawing can be modified close to
p
1
so as to separate all edges
p
i
p
j
from each
other. This introduces at most one more bend per edge, so that the resulting edges have
Pach and Wenger, we can create edges
p
i
p
j
∈
