Information Technology Reference
In-Depth Information
tion in simultaneousplanardrawingsis
NP
-hard, since it is
NP
-hard to decide whether
there is a straight-line simultaneousdrawing [9]. Crossing minimization in simultane-
ousplanardrawingsisalso
NP
-hard, as follows from an
NP
-hardness result on
an-
chored planardrawings
by Cabello and Mohar [5] (see Section 4).
As mentioned above, the special cases of PEG and SEFE in which there are no edges
in the pre-drawn subgraphandinthecommonsubgraph have been already studied.
ConcerningPEG, Pach and Wenger [20] proved the following result: given an
n
-
vertex planar graph
G
with fixed vertex locations, a planar drawing of
G
in which each
edge has at most 120
n
bends can be constructed in
O
(
n
2
) time. They also proved that
such a bound is tight in the worst case. A 3
n
+2upper bound improvingupon the 120
n
upper bound of Pach and Wenger has been proved by Badent et al. [2].
Concerning SEFE, Erten and Kobourov[8]provedthefollowing result: given two
planar graphs
G
1
and
G
2
sharing some vertices and no edges with a total number of
n
vertices, there is an
O
(
n
)-time algorithm to construct a simultaneousplanardrawing of
G
1
and
G
2
on a grid of size
O
(
n
2
)
O
(
n
2
), with at most 3 bends per edge, hence at
most 16 crossings between any edgeof
G
1
and any edgeof
G
2
.Building on Kaufmann
and Wiese'sdrawing algorithm [17], the number of bends per edgeandthenumber of
crossings per pair of edges can be reduced to 2 and 9, respectively, at the expense of an
exponential increase in the area of the simultaneousdrawing.
Haeupler et al. [13] showed that if two simultaneously planar graphs
G
1
and
G
2
share a subgraph
G
that is connected, then there is a simultaneousplanardrawing in
which any edgeof
G
1
−
×
G
intersect at most once. Introducing
vertices at crossing points yields a planar graph, and a straight-line drawing of that graph
provides a simultaneousplanardrawing with
O
(
n
) bends per edge,
O
(
n
) crossingsper
edge, and with vertices, bends, and crossingsonan
O
(
n
2
)
G
and any edgeof
G
2
−
O
(
n
2
) grid. Ourresult
generalizes this to the case where the common graph
G
is not necessarily connected.
×
1.2
Graph Drawing Terminology
A
rotation system
for a graph is a cyclic ordering of the edges incident to each vertex. A
rotation system of a connected graph determines its
facial walks
—the closed walks in
which each edge (
u,v
) is followed by the next edge (
v,w
) in the cyclic order at
v
.The
facial walks are the boundaries of the
faces
in an embedding of the graph. The
size
|
of a facial walk
W
is the length of
W
(edge repetitions are counted). A rotation system
is
planar
if it corresponds to a planar drawing;a
planarembedding
of a connected
graph consists of a planar rotation system together with a specified outer face.
These definitions do not handle the situation in which the graph is not connected.
Following Junger and Schulz [16], we define a
topologicalembedding
of a (possibly
non-connected) graph as follows: We specify a planar embedding for each connected
component. This determines a set of inner faces. For each connected component we
specify a “containing” face, which may be an inner face of some other component or the
uniqueouter face. Furthermore, we forbid cycles of containment—in other words, if a
connected component is contained in an inner face, which is contained in a component,
etc., then this chain of containments must lead eventually to the uniqueouter face.
A
facialboundary
in a topological embedding of a graph is the collection of facial
walks along the (not necessarily connected) boundary of a face. Each face (unless it is
|
W
