Information Technology Reference
In-Depth Information
the outer face) has a distinguished facial walk we call the
outer
facial walk separating
the remaining
inner
facial walks from the outer face of the embedding.The
size
of a
facial boundary is the sum of the sizes of the facial walks part of the facial boundary.
A
compatible embedding
of two planar graphs
G
1
and
G
2
consists of topological
embeddingsof
G
1
and
G
2
such that the common subgraph
G
inherits the same topo-
logical embedding from
G
1
as from
G
2
(where a subgraph inherits a topological embed-
ding in a straightforward way; in particular, if we remove an edge that disconnects the
graph, the face containment is determined by the edge that was removed). Junger and
Schulz [16] proved that
G
1
and
G
2
are simultaneously planar if and only if they have
a compatible embedding. For that proof, they construct a simultaneousplanardrawing
of
G
1
and
G
2
by extending adrawing of
G
(thusproving aformofour Theorem 1).
However, their method does not yield any bounds on the number of bends or crossings.
2
Partially Embedded Graphs
In this section we prove Theorem 1. We will construct a planar drawing of
G
that
extends
H
,assuming that we are given a planar embedding of
G
that extends
H
.It
suffices to prove the result for a single face
F
of
and the connected components of
G
that lie inside or on the boundary of
F
and are connected to
H
.
Pach and Wenger [20] proved their upper bound on the number of bends needed to
draw a graph with fixed vertex locations by drawing a tree with leaves at the fixed vertex
locations, and “routing” all the edges close to the tree, sometimes crossing the tree but
never crossing each other. We will adapt their method to our setting.
One important difference is that we have to deal with fixed facial boundaries instead
of fixed vertex locations. The solution is natural: We contract each facial boundary
W
i
of
F
to a single vertex
v
i
,fixvertex
v
i
inside
F
near
W
i
, and then apply the Pach-
We nger method to draw the contracted graph on the fixed vertex locations
v
i
.Thismust
be done while keeping the drawing inside
F
. We keep the drawing at a small distance
from the boundary of
F
, inside a polygonal region
F
that is an “inner approximation”
of
F
.Inside
F
we draw a tree
T
with its leaves
v
i
at the fixed vertex locations, suitably
bounding the size of
T
in order to get ourbound on the number of bends. We then route
the edges of the contracted graph close to
T
as in Pach-Wenger. Finally, to get back our
uncontracted graph, we route the edges incident to
v
i
to their true endpoint on the facial
boundary
W
i
—these routes use the empty buffer zone between
F
and
F
.
We now fill in further details. We use
n
A
and
m
A
for the number of vertices and
edges in subgraph
A
.Let
W
i
, with 1
H
b
, be the boundary walks of
F
.
We now introduce the concept of inner
ʵ
-approximations. The
Hausdorff distance
d
H
(
A, B
) of two sets (in a space with metric
d
)isdefinedas:
2
max
≤
i
≤
.
Intuitively, the Hausdorff distance measures how far a point in one set can be from
the other set. Sets
A
and
B
are
ʵ
-close
if
d
H
(
A, B
)
<ʵ
.Then
A
is an
inner
ʵ
-
approximation of
B
if they are
ʵ
-close and there is a
ʴ>
0 so that all the points
ʴ
-close
to
A
are a subset of
B
. The next lemma deals with inner
ʵ
-approximations of
F
.
{
sup
a∈A
inf
b∈B
d
(
a, b
)
,
sup
b∈B
inf
a∈A
d
(
a, b
)
}
2
The underlying metric
d
can be Euclidean or some other appropriate metric.
