Information Technology Reference
In-Depth Information
then weak realizability of (
G, R
) expresses a simultaneous planarity problem
for two graphs: if
R
is a complete bipartite graph on
E
1
(
G
)and
E
2
(
G
), and
E
0
(
G
) contains the remaining (isolated) vertices of
E
(
G
), then (
G, R
)isweakly
realizable, if and only if
G
1
with edge set
E
0
(
G
)
∪
E
1
(
G
)and
G
2
with edge set
E
0
(
G
)
E
2
(
G
) have a simultaneous embedding with fixed edges. The complexity
of this problem is famously open, and related to several other open problems in
graph drawing (e.g.
c
-planarity [21]). If
R
is a complete
k
-partite graphs, then
the weak realizability problem corresponds to the sunflower case of the SEFE
problem for
k
graphs, which is
NP
-complete even for
k
= 3 [3,21].
If
R
consists of two disjoint complete graphs that together partition the vertex
set
E
(
G
), we get a problem which is the opposite of the SEFE problem: it asks
whether we can draw the two graphs
G
1
and
G
2
simultaneously (so that shared
edges are drawn the same way) so that edges belonging to the same graph may
cross each other, but edges belonging to different graphs may not. As far as we
know, nobody has investigated this version of the problem. Even the case where
R
is a tree (or even a matching) does not seem immediately obvious.
∪
References
1. Angelini, P., Binucci, C., Da Lozzo, G., Didimo, W., Grilli, L., Montecchiani, F.,
Patrignani, M., Tollis, I.G.: Drawings of non-planar graphs with crossing-free sub-
graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 292-303.
Springer, Heidelberg (2013)
2. Angelini, P., Di Battista, G., Frati, F., Jelınek, V., Kratochvıl, J., Patrignani,
M., Rutter, I.: Testing planarity of partially embedded graphs. In: Proceedings of
the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2010, pp. 202-221. Society for Industrial and Applied Mathematics, Philadelphia
(2010)
3. Angelini, P., Da Lozzo, G., Neuwirth, D.: On some
NP
-complete SEFE problems.
In: Pal, S.P., Sadakane, K. (eds.) WALCOM 2014. LNCS, vol. 8344, pp. 200-212.
Springer, Heidelberg (2014)
4. Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number
and 1-planarity hard. SIAM Journal on Computing 42(5), 1803-1829 (2013)
5. Canny, J.: Some algebraic and geometric computations in pspace. In: STOC 1988:
Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing,
pp. 460-469. ACM, New York (1988)
6. Chojnacki, C. (Hanani, H.): Uber wesentlich unplattbare Kurven im drei-
dimensionalen Raume. Fundamenta Mathematicae 23, 135-142 (1934)
7. de Longueville, M.: A course in topological combinatorics. Universitext. Springer,
New York (2013)
8. Eggleton, R.B.: Rectilinear drawings of graphs. Utilitas Math. 29, 149-172 (1986)
9. Eppstein, D.: Big batch of graph drawing preprints,
http://11011110.
livejournal.com/275238.html
(last accessed September 4, 2013)
10. Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few cross-
ings per edge. Algorithmica 49(1), 1-11 (2007)
11. Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with Hanani-Tutte
for testing
c
-planarity. In: McGeoch, C.C., Meyer, U. (eds.) 2014 Proceedings of
the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX),
pp. 86-97. SIAM (2014)
