Information Technology Reference
In-Depth Information
this paper we show how to draw
G
while preserving the actual drawing
of
H
,sothat
each edge has a linear number of bends. This bound is worst-case optimal, as proved by
Pach and Wenger [20] in the special case in which
H
has no edges.
Aresult analogoustoours was claimed by Fowler et al. [10] for the special case in
which
H
has the same vertex set as
G
.Theiralgorithm draws the edges of
G
one by
one in a certain order, and they claim a linear number of bends per edge. However, we
giveanexamplewheretheiralgorithm produces exponentially many bends, confirming
a claim of Schaefer [23] that greedy extensions can in general give many bends.
We also address the
simultaneousplanarity
problem [4], also known as “simulta-
neous embedding with fixed edges (SEFE)”. The SEFE problem is strongly related
to the partially embedded graph problem and—in a sense we will make precise later—
generalizes it. We are given two planar graphs
G
1
and
G
2
that share a
common subgraph
G
(i.e.,
G
is composed of those vertices and edges that belong to both
G
1
and
G
2
). We
wish to find a
simultaneously planardrawing
,i.e.,aplanardrawing of
G
1
and a planar
drawing of
G
2
that coincide on
G
. Graphs
G
1
and
G
2
are
simultaneously planar
if they
admit such a drawing.Both
G
1
and
G
2
may have
private
edges that are not part of
G
.
In a simultaneousplanardrawing the private edges of
G
1
may cross the private edges
of
G
2
.Thesimultaneous planarity problem arises in information visualization when we
wish to display two relationships on two overlapping element sets.
The decision version of the simultaneous planarity problem is not known to be
NP
-
complete, nor solvable in polynomial time, thoughitis
NP
-complete if more than two
graphs are given [11]. However, there is a combinatorial characterization of simultane-
ous planarity, based on the concept of a “compatible embedding”, duetoJunger and
Schulz [16] (see below for details). Erten and Kobourov [8], who first introduced the
problem, gave an efficient drawing algorithm for the special case where the two graphs
share vertices butnoedges. In this case, a simultaneousplanardrawing always exists,
and they construct a drawing in which each edge has at most three bends and therefore
any two edges cross (when they legally can) at most 16 times. In this paper we show
that if two graphs have a simultaneousplanardrawing, then there is a drawing in which
every edge has a linear number of bends and in which any two edges cross at most 24
times. Ourresult is algorithmic, assuming a compatible embedding is given.
More formally, our paper addresses the following two problems:
H
- Planarity of a partially embedded graph (PEG).
Given a planar graph
G
and a
straight-line planar drawing
H
of a subgraph
H
of
G
, find a planar drawing of
G
(see [1,15]).
- Simultaneous planarity (SEFE).
Given two planar graphs
G
1
and
G
2
that share
asubgraph
G
, find planar drawingsof
G
1
and
G
2
that are the same on the shared
subgraph (see [4]).
that extends
H
We prove the following results:
Theorem 1.
Let
G
be an
n
-vertex planar graph,let
H
be a subgraph of
G
, andlet
H
be a straight-lineplanardrawing of
H
. Suppose that
G
has a planarembedding
E
that
.Thenwecan construct a planardrawing of
G
in
O
(
n
2
)
-time which realizes
extends
H
E
,extends
H
, and has at most
102
|
V
(
H
)
|
+12
bends per edge.
