Planar and Quasi Planar Simultaneous Geometric Embedding - Graph Drawing - page 62

5 Discussion and Open Problems

Several open problems arise from the study of the SGQPE:
Problem 1. Fowler and Kobourov [11] characterized AEPgraphs, while in this paper
we provided a characterization of EAPgraphs. Thus the first obvious open problem is
to characterize AEQP and EAQPgraphs.
Problem 2. Does every pair of trees (or even every pair of planar graphs) admit a
SGQPE?Sofarwewereonlyabletoprovethefollowing.

Theorem 8. There exists a pair of quasi planar graphsthat does not admit aSGQPE.

Problem 3. Extend the study of simultaneous embeddability to other families of draw-
ings with forbidden crossing configurations, such as k -planar, RAC, LAC, fan-planar,
fan-crossing-free-planar drawings.

References

1. Ackerman, E., Tardos, G.: On the maximumnumber of edges in quasi-planar graphs. J. of
Combinatorial Theory, Series A 114(3), 563-571 (2007)
2. Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear
number of edges. Combinatorica 17(1), 1-9 (1997)
3. Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric
simultaneous embedding.J.ofGraphAlgorithms and Applications 16(1), 37-83 (2012)
4. Blasius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamas-
sia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2014)
5. Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G.,
Lubiw, A., Mitchell, J.S.B.: On simultaneousplanargraph embeddings. In: Dehne, F., Sack,
J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 243-255. Springer, Heidelberg
(2003)
6. Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lu-
biw, A., Mitchell, J.S.B.: On simultaneousplanargraph embeddings. Comput. Geom. 36(2),
117-130 (2007)
7. Cabello, S., van Kreveld, M.J., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.: Geomet-
ric simultaneous embeddingsofagraph and a matching.J.GraphAlgorithms and Applica-
tions 15(1), 79-96 (2011)
8. Didimo, W., Kaufmann, M., Liotta, G., Okamoto, Y., Spillner, A.: Vertex angle and crossing
angle resolution of leveled tree drawings. Inform. Process. Lett. 112(16), 630-635 (2012)
9. Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level
planar trees. Computational Geometry 42(6-7), 704-721 (2009)
10. Evans, W., Kusters, V., Saumell, M., Speckmann, B.: Column planarity and partial simultane-
ous geometric embedding.In:Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871,
pp. 259-271. Springer, Heidelberg (2014)
11. Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar graphs. In: Hong,
S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 37-49. Springer, Hei-
delberg (2008)
12. Fox, J., Pach, J., Suk, A.: The number of edges in k -quasi-planar graphs. SIAM J. on Discrete
Mathematics 27(1), 550-561 (2013)
13. Valtr, P.: On geometric graphs with no k pairwise parallel edges. Discrete & Computational
Geometry 19(3), 461-469 (1998)