Information Technology Reference
In-Depth Information
4
Simultaneous Planarity
Before turning to ouralgorithm for drawing simultaneously planar graphs, we justify
our claim that minimizing the number of crossingsinasimultaneousplanardrawing
is
NP
-hard. This result follows from Cabello and Mohar's proof of
NP
-hardness for
the
anchored planarity
problem [5, Theorem 2.1], but a more direct proof of a slightly
stronger result is possible by reduction from the
NP
-complete crossing number prob-
lem. We briefly explain the reduction. Given a graph
G
with
m
edges, subdivide each
edge 2
m
times. Let
G
1
consist of all the edges incident to the original vertices of
G
together with every other edgealong the paths connecting the original vertices. Let
G
2
consist of the remaining edges. Note that
G
1
and
G
2
do not share any edges. It can
be easily seen that the crossing number of
G
equals the smallest number of crossings
between edges of
G
1
and edges of
G
2
in a simultaneousdrawing of
G
1
and
G
2
.
4
We
now turn to the proof of Theorem 2.
Proof (of Theorem 2).
We show how to find in
O
(
n
2
) time a simultaneousplanardraw-
ing
ʓ
such that any private edgeof
G
1
and any private edgeof
G
2
intersect at most 24
times, such that every edgeof
G
1
is straight, and such that every private edgeof
G
2
has
at most 102
+12bends. In order to construct a simultaneousplanardrawing
ʓ
|
V
(
H
)
|
on an
O
(
n
2
)
O
(
n
2
) grid such that any private edgeof
G
1
and any private edgeof
G
2
intersect at most 24 times, such that each edgeof
G
is straight, and such that every
private edge has at most 72
n
bends, it suffices to introduce dummy vertces at the
O
(
n
2
)
crossing points in
ʓ
, and then to construct a straight-line drawing of the resulting planar
graph on a small grid. In particular, the number of bends per edgein
ʓ
is at most 72
n
,
since each edgein
ʓ
crosses less than 3
n
edges, each at most 24 times.
We start by constructing any straight-line planar drawing
ʓ
1
of
G
1
. We now construct
adrawing
ʓ
2
of
G
2
by exploiting an approach analogous to the one of the proof of
Theorem 1. Drawing
ʓ
1
induces a straight-line planar drawing
ʓ
of
G
.Thus, in order
to determine
ʓ
2
, it remains to describe how to draw the private edges of
G
2
. We will
accomplish this independently for each face
F
of
G
.
We construct a triangulation
ʣ
of
F
by using all the vertices and edges of
G
1
that
lie inside
F
,aswellassomeextraedges. Next, we execute the same algorithm as for
the proof of Theorem 2. Namely, we construct a straight-line drawing of the dual
D
of
ʣ
and we take a spanning tree
T
of
D
. For each boundary walk
W
i
of
F
,weaugment
T
with a leaf
v
i
close to
W
i
and inside
F
,where
F
is an inner
ʵ
-approximation of
F
.Let
G
2
be the embedded multi-graph obtained by restricting
G
2
to the vertices and
edges inside or on the boundary of
F
, and by contracting each boundary walk
W
i
of
F
to a single vertex
v
i
.WeuseLemma3toconstruct a planar poly-line drawing of
G
2
that realizes the given embedding,thatis
ʵ
-close to
T
, and in which vertices
v
i
maintain
their fixed locations. Finally, we reconnect edges in
G
2
to the boundary components
they belong to. In order to do this, we first “wrap” the edges of
G
2
passing by a vertex
×
4
Using the fact that crossing number is hard for cubic graphs [14], we can even show that
minimizing the number of crossingsinasimultaneousdrawing of two graphs one of which is
the disjoint union of paths of length at most two and the other is a matching is
NP
-hard. This
is in some sense sharp, since the union of two matchingsisalwaysplanar.
