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 ,
Search WWH ::




Custom Search