Information Technology Reference
In-Depth Information
1 bends. Finally, note that each edge
p
i
p
j
comes close
to each leaf of
T
(including
p
1
) at most twice, once for
Δ
i,k
and once for
Δ
j,k
.
|
E
(
T
)
|−
|
E
(
T
)
|−
2(2
1)+1 = 4
Now we are ready to finish the proof of Lemma 3. We show how to apply Lemma 6
in case
G
is not Hamiltonian, and not all its vertices are assigned fixed locations.
By Lemma 4, we can construct a graph
G
with a Hamiltonian cycle
C
by sub-
dividing each edgeof
G
at most twice, and by adding some edges, where
G
has a
planar embedding extending the embedding of
G
. Traverse
C
: whenever we encounter
an edgeof
C
with at least one endpoint not in
U
, contract that edge. This yields a new
Hamiltonian graph
G
with
V
(
G
)=
U
and a planar embedding induced by the planar
embedding of
G
. Use Lemma 6 to embed
G
at the fixed vertex locations, and
ʵ
-close
to
T
, so that each edgeof
G
has at most 4
|E
(
T
)
|−
1 bends. Each vertex
u ∈ U
of
G
corresponds to a set of vertices
V
u
ↆ
V
(
G
) which was contracted to
u
,sothesubgraph
G
u
of
G
induced by
V
u
is connected. Since we embedded
G
with the induced planar
embedding of
G
, we can now do some surgery to turn
u
back into
G
u
.
To this end, we define a graph
G
u
, which consists of
G
u
,ofacycle
C
u
containing
G
u
in its interior, and of some further edges. Each vertex of
C
u
corresponds to an edge
of
G
“incident to”
G
u
, i.e., with an end-vertex in
V
u
and with an end-vertex not in
V
u
.
Vertices appear in
C
u
in the same order as the corresponding edges incident to
G
u
leave
G
u
(this order also corresponds to the cyclic order of the edges incident to
v
in
G
);
each vertex of
C
u
corresponding to an edge
e
of
G
is connected to the end-vertex of
e
in
V
u
. Finally,
G
u
contains further edges that triangulate its internal faces.
Now consider a small disk
ʴ
around
u
. We erase the part of the drawing of
G
inside
ʴ
. We construct a straight-line convex drawing of
G
u
in which each vertex of
C
u
is mapped to the point in which the corresponding edge crosses the boundary of
ʴ
.Thisdrawing always exists (and can be constructed efficiently), given that
G
u
is 2-
connected and internally-triangulated. Removing the edges that triangulate the internal
faces of
G
u
completes the reintroduction of
G
u
.
Overall, we added one bend to an edge with exactly one endpoint in
V
u
. Since an
edge can have endpoints in at most two
V
u
, this process adds at most two bends per
edge, so every edge has at most 4
+1 bends. Since each edgeof
G
was subdivided
at most twice to obtain
G
, each edgeof
G
has at most 3(4
|
E
(
T
)
|
|
E
(
T
)
|
+1)+2=12
|
E
(
T
)
|
+
5
<
12
bends. Each edgeof
G
comes close to each leaf of
T
at most twice, so
each edgeof
G
comes close to each vertex of
U
at most six times. This concludes the
proof of Lemma 3.
|
V
(
T
)
|
3
Extending Partial Straight-Line Planar Drawings Greedily
Let
G
be an
n
-vertex plane graph, let
H
be a spanning subgraph of
G
,let
be a
straight-line planar drawing of
H
,andlet
˃
=[
e
1
,...,e
m
] be an ordering of the edges
in
G
H
with respect to
˃
if it is obtained
by drawing edges
e
1
,...,e
m
in this order, so that
e
i
is drawn as a polygonal curve that
respects the embedding of
G
and with the minimumnumber of bends, for
i
=1
,...,m
.
Fowler
et al.
claimed in [10] that, for every ordering
˃
of the edges in
G
\
H
.Adrawing
ʓ
of
G
greedily extends
H
H
such that
the edges between distinct connected components of
H
precede edges between vertices
\
