Abstract
We consider the following problem known as simultaneous geometric graph embedding (SGE). Given a set of planar graphs on a shared vertex set, decide whether the vertices can be placed in the plane in such a way that for each graph the straight-line drawing is planar. We partially settle an open problem of Erten and Kobourov [5] by showing that even for two graphs the problem is NP-hard.
We also show that the problem of computing the rectilinear crossing number of a graph can be reduced to a simultaneous geometric graph embedding problem; this implies that placing SGE in NP will be hard, since the corresponding question for rectilinear crossing number is a long-standing open problem. However, rather like rectilinear crossing number, SGE can be decided in PSPACE.
Partially supported by Marie-Curie Research Training Network (ADONET) and by the German Science Foundation (JU204/10-1).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443–459 (1991)
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)
Brass, P., Moser, W., Pach, J.: Research problems in discrete geometry. Springer, New York (2005)
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 (1988)
Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 195–205. Springer, Heidelberg (2005)
Frati, F.: Embedding graphs simultaneously with fixed edges. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 108–113. Springer, Heidelberg (2007)
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316 (1983)
Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 325–335. Springer, Heidelberg (2006)
Geyer, M., Kaufmann, M., Vrt’o, I.: Two trees which are self-intersecting when drawn simultaneously. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 201–210. Springer, Heidelberg (2006)
Di Giacomo, E., Liotta, G.: A note on simultaneous embedding of planar graphs. In: 21st European Workshop on Comp.Geometry, pp. 207–210 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Estrella-Balderrama, A., Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M. (2008). Simultaneous Geometric Graph Embeddings. In: Hong, SH., Nishizeki, T., Quan, W. (eds) Graph Drawing. GD 2007. Lecture Notes in Computer Science, vol 4875. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77537-9_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-77537-9_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77536-2
Online ISBN: 978-3-540-77537-9
eBook Packages: Computer ScienceComputer Science (R0)