Information Technology Reference
In-Depth Information
4 Future Research
What can we say about traditional approaches to partial planarity? More specif-
ically, can
PQ
-trees or
SPQR
-trees be used to solve this problem?
Recall that a
bridge
of
S
in
G
is either an edge in
E
(
G
)
E
(
S
) with both
endpoints in
S
(a
trivial
bridge) or a connected component of
G
−
S
together
with its edges and vertices of attachment to
S
. Given an embedding of
S
,a
group of vertices of
S
is
mutually visible
[2] if there is a face of
S
containing all
vertices in the group on its boundary. The poly-line variant can be rephrased
as follows: is there a poly-line embedding of
S
so that for every bridge of
S
in
G
, the vertices of attachment of the bridge are mutually visible? It seems quite
likely that SPQR-trees could be used to decide that question, even in linear time,
extending ideas for deciding partially embedded planarity developed in [2].
Another solution may come from progress on simultaneous embeddings, since
partial planarity can be viewed as a special case of simultaneous planarity.
2
Two
graphs
G
1
,
G
2
are
simultaneously planar
if there is a drawing of
G
1
∪
−
G
2
in
which the induced drawings of
G
1
and
G
2
are (each by itself) planar. Given a
graph
G
and
S
,weaddedgesin
S
to both
G
1
and
G
2
. All other edges
E
(
G
)
−
S
we subdivide 2
times, and assign the pieces along each subdivided edge
of
G
to
G
1
and
G
2
alternatingly. If
G
has a drawing in which all edges in
S
are
crossing-free, we can turn this into a simultaneous drawing of
G
1
and
G
2
,since
we can assume that any two edges in
E
(
G
)
|
E
(
G
)
|
−
S
cross at most once, so every edge
has less than
crossings which we can now realize by matching up
G
1
and
G
2
pieces of the subdivided edges.
|
E
(
G
)
|
Weak Realizability
Before we leave partial planarity, we want to draw one more connection, to the
weak realizability
problem introduced by Kratochvıl [15,16]: Given a graph
G
and a symmetric relation
R
on
E
(
G
), we can ask whether the
abstract topological
graph
(
G, R
)is
weakly realizable
, that is, if there is a drawing in which only pairs
of edges (
e,f
)
R
are allowed to cross (but do not have to cross). The general
problem is
NP
-complete [15,23], so one could ask whether there are special cases
which are solvable. Let us shift the focus by viewing
R
itself as the edge set of
a graph on the vertex set
E
(
G
).
From this point of view,
R
=
∈
corresponds to the planarity problem for
G
, which can be solved in linear time. On the other hand, letting
R
be the
complete graph on
E
(
G
) leads to a trivial problem. What happens if we let
R
be a complete graph on a subset
E
ↆ
∅
E
(
G
) of all edges of
G
? It turns out that
this captures partial planarity: (
G, R
) is weakly realizable, if and only if (
G, E
)
is partially planar.
This could be the starting point of an attack on weak realizability using
structural properties of
R
, an approach from the intersection-graph point of
view. We quickly get into uncharted waters: If
R
is a complete bipartite graph,
2
This is based on a suggestion by Ignaz Rutter.
