Information Technology Reference
In-Depth Information
Theorem 2.
Let
G
1
and
G
2
be simultaneously planar graphsonatotalof
n
vertices
withashared subgraph
G
.Then there is a simultaneousplanardrawing inwhich any
edgeof
G
1
−
G
and any edgeof
G
2
−
G
intersect at most
24
times, andoneofthe
following properties holds:
1. each edgeof
G
is straight, andeach private edgeof
G
1
andof
G
2
has at most
72
n
bends; also, vertices, bends, and crossings lie onan
O
(
n
2
)
O
(
n
2
)
grid; or
2. each edgeof
G
1
is straight andeach private edgeof
G
2
has at most
102
×
|
V
(
H
)
|
+12
bends per edge.
If we are givenacompatible embedding of thetwo graphs, wecan construct such draw-
ingsin
O
(
n
2
)
time.
Theorem 1 generalizes Pach and Wenger'sresult, which corresponds to the special
case in which the pre-drawn subgraph has no edges. Observe that Theorem 1 directly
provides a weak form of Theorem 2: If
G
1
and
G
2
are simultaneously planar, then they
admit a compatible embedding. We can hence take any straight-line planar drawing of
G
1
realizing the embedding and extend the induced drawing of
G
to a drawing of
G
2
.
By Theorem 1, we obtain a simultaneousplanardrawing where each edgeof
G
1
is
straight and each private edgeof
G
2
has at most 102
+12bends per edge. Our
stronger result of 24 crossings between any two edges is obtained by modifying the
proof of Theorem 1, rather than applying that result directly.
We note that Grilli et al. [12] have a paper in this conference with a result similar
to Theorem 2. They show, using different techniques, that two simultaneously planar
graphs have a simultaneousplanardrawing with at most 9 bends per edge, vastly better
than our 72
n
bound. Our primary goal, however, was to reduce crossings rather than
bends. We achieve 24 crossings per pair of edges. They do not address the number of
crossings, but the obviousbound from their result is 100 crossings per pair of edges.
We also achieve a polynomial-size grid, but the obvious way of forcing their drawing
onto a polynomial-sized grid increases the number of bends per edgeto300
n
.
|
V
(
H
)
|
1.1 Related Work
The decision version of simultaneous planarity generalizes partially embedded pla-
narity: given an instance (
G, H,
to a draw-
ing of a 3-connected graph
G
1
and let
G
2
=
G
.Then
G
1
and
G
2
are simultaneously
planar if and only if
G
has a planar embedding extending
H
) of the latter problem, we can augment
H
. In the other direction, the
algorithm [1] for testing planarity of partially embedded graphs solves the special case
of the simultaneous planarity problem in which the embedding of the common graph
G
is fixed (which happens, e.g., if
G
or one of the two graphs is 3-connected).
Several optimization versions of partially embedded planarity and simultaneouspla-
narity are
NP
-hard. Patrignani showed that testing whether there is a straight-line draw-
ing of a planar graph
G
extending a given drawing of a subgraph of
G
is
NP
-complete
[21], so bend minimization in partial embedding extensions is
NP
-complete; Patrig-
nani'sresult holds even if a combinatorial embedding of
G
is given.
1
Bend minimiza-
1
Patrignani does not explicitly claim
NP
-completeness in the case in which the embedding of
G
is fixed, but that can be concluded by checking his construction; only the variable gadget,
picturedinhisFigure 3, needs minor adjustments.
H
