Information Technology Reference
In-Depth Information
has to be planar (crossing-free) or not: we can pick the planar edges. Looking
at planarity as a local requirement opens it up for combination with other prop-
erties; for example, what happens if we can specify a bound on the number of
crossings along each edge, or on the number of bends?
Previous Research
Angelini, et al. [1] show that (
G, S
) is always partially planar if
S
is a spanning
tree of
G
, even if the embedding of
S
is required to be a straight-line embedding.
For geometric partial planarity, they show that (
G, S
) can always be realized if
S
is a spanning spider or caterpillar, even in polynomial area. However, they
also exhibit examples of (
G, S
)where
S
is a spanning tree of
G
for which (
G, S
)
has no geometric partial realization. There are further algorithms in the paper
to test geometric partial planarity for various types of spanning trees
S
, though
in some cases the layout algorithms require exponential area.
Our Contribution
In Section 2 we show that using a Hanani-Tutte style approach successfully
settles the complexity of the poly-line variant of the problem: partial planarity
can be solved in polynomial time. This is a further example of a planarity-style
problem for which there is (as yet) no traditional polynomial-time algorithm for
the problem, but the Hanani-Tutte approach leads to a solution. Other examples
of this are surveyed in [21].
We have to leave the complexity of the straight-line variant open, but there is a
good chance that it is as hard as the existential theory of the reals (see [20]). One
indication for this is that the layout algorithm for geometric partial planarity
suggested in [1] needs exponential area on some inputs. Secondly, the result is
true if we replace planarity with 1-planarity: testing partial geometric 1-planarity
is as hard as the existential theory of the reals, as we will see in Section 3.
In comparison, the special case of geometric 1-planarity is
NP
-complete (this
follows from known results in the literature, see Theorem 2).
2 Partial Planarity and Hanani-Tutte
We assume that the reader is somewhat familiar with the Hanani-Tutte charac-
terization of planarity (see [21,22]). Briefly, Hanani [6] and Tutte [27] established
the following algebraic characterization of planar graphs: a graph is planar if and
only if it has a drawing in which every two independent edges cross evenly. This
criterion can be rephrased as a linear system over GF(2): Create variables
x
e,v
for every
e
V
(
G
), and let
i
D
(
e,f
) denote the number of times
two edges
e
and
f
cross in a drawing
D
of
G
. Fix an arbitrary drawing
D
of
G
(e.g. a convex drawing). Let
P
(
D
) be the system of linear equations over GF(2)
containing:
∈
E
(
G
)and
v
∈
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
≡
0mod2
,