Information Technology Reference
In-Depth Information
Picking Planar Edges; or, Drawing a Graph
with a Planar Subgraph
Marcus Schaefer
School of Computing, DePaul University, Chicago, IL 60604, USA
mschaefer@cdm.depaul.edu
Abstract.
Given a graph
G
and a subset
F ↆ E
(
G
) of its edges, is there
adrawingof
G
in which all edges of
F
are free of crossings? We show
that this question can be solved in polynomial time using a Hanani-Tutte
style approach. If we require the drawing of
G
to be straight-line, but
allow up to one crossing along each edge in
F
, the problem turns out to
be as hard as the existential theory of the real numbers.
1 Introduction
Angelini, Binucci, Da Lozzo, Didimo, Grilli, Montecchiani, Patrignani, and Tol-
lis [1] asked the following problem:
“Given a non-planar graph
G
and a planar subgraph
S
of
G
, decide
whether
G
admits a drawing
ʓ
such that the edges of
S
are not crossed
in
ʓ
, and compute
ʓ
if it exists”.
Their paper studies two variants of this problem: the unrestricted problem in
which
ʓ
is an arbitrary poly-line drawing, and the straight-line variant, in which
ʓ
is restricted to straight-line drawings. Let us call these the
partial planarity
and the
geometric partial planarity
problem. It seems that these two problems are
new to the literature. The closest previous variant may be the (also very recent)
notion of partially embedded planarity [2], which differs in that a particular
embedding of
S
is given, and the desired planar embedding of
G
has to extend
the given embedding of
S
. For partially embedded planarity, a linear-time testing
algorithm is known [2], as well as an obstruction set [13].
David Eppstein commented on the paper by Angelini et al. [1] in his blog [9]:
“If you're given a graph in which some edges are allowed to participate
in crossings while others must remain uncrossed, how can you draw it,
respecting these constraints? Unfortunately the authors were unable to
determine the computational complexity of this problem, and leave it as
an interesting open problem”.
In other words, given a graph
G
and a subset of its edges
F
E
(
G
), is there
a (straight-line) drawing of
G
in which all edges of
F
are free of crossings? The
subgraph and subset formulations are equivalent, of course, but we slightly pre-
fer the second, since it emphasizes that we can specify for each edge whether it
ↆ
