Planar and Quasi Planar Simultaneous Geometric Embedding

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2014) Planar and Quasi Planar Simultaneous Geometric Embedding. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 52-63 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_5).

Full text not available from this repository.

Abstract

A simultaneous geometric embedding (SGE) of two planar graphs G 1 and G 2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G 1 and Γ2 of G 2 such that each vertex is drawn at the same point in Γ1 and Γ2. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where Γ1 and Γ2 are required to be quasi planar (i.e., they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up to several new interesting research questions.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_5
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Z Theory > Z.999 Others
ID Code:1421

Repository Staff Only: item control page

References

Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. of Combinatorial Theory, Series A 114(3), 563–571 (2007)

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)

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. J. of Graph Algorithms and Applications 16(1), 37–83 (2012)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2014)

Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 243–255. Springer, Heidelberg (2003)

Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom. 36(2), 117–130 (2007)

Cabello, S., van Kreveld, M.J., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.: Geometric simultaneous embeddings of a graph and a matching. J. Graph Algorithms and Applications 15(1), 79–96 (2011)

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)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Computational Geometry 42(6-7), 704–721 (2009)

Evans, W., Kusters, V., Saumell, M., Speckmann, B.: Column planarity and partial simultaneous geometric embedding. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 259–271. Springer, Heidelberg (2014)

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, Heidelberg (2008)

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)

Valtr, P.: On geometric graphs with no k pairwise parallel edges. Discrete & Computational Geometry 19(3), 461–469 (1998)