Simultaneous Geometric Graph Embeddings

Estrella-Balderrama, Alejandro and Gassner, Elisabeth and Jünger, Michael and Percan, Merijam and Schaefer, Marcus and Schulz, Michael (2008) Simultaneous Geometric Graph Embeddings. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 280-290 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_28).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_28
Classifications:P Styles > P.999 Others
G Algorithms and Complexity > G.490 Embeddings
ID Code:845

Repository Staff Only: item control page

References

Daniel Bienstock. Some provably hard crossing number problems. Discrete Comput. Geom., 6(5):443-459, 1991.

Peter Brass, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan Ismailescu, Stephen G. Kobourov, Anna Lubiw, and Joseph S. B. Mitchell. On simultaneous planar graph embeddings. In Workshop on Algorithms and Data Structures, Volume 2748 of Lecture Notes in Computer Science, pages 243-255. Springer-Verlag, 2003.

Peter Brass, William Moser, and János Pach. Research problems in discrete geometry. Springer-Verlag, New York, 2005.

John Canny. Some algebraic and geometric computations in pspace. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460-469, 1988.

Cesim Erten and Stephen G. Kobourov. Simultaneous embedding of planar graphs with few bends. In J. Pach, editor, 12th Int. Symp. on Graph Drawing, volume 3383 of Lecture Notes in Computer Science, pages 195-205. Springer-Verlag 2005.

Fabrizio Frati. Embedding graphs simultaneously with fixed edges. In M. Kaufmann and D. Wagner, editors, 14th Int. Symp. on Graph Drawing, volume 4372 of Lecture Notes in Computer Science, pages 108-113. Springer-Verlag, 2007.

Michael R. Garey and David S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983.

Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, and Michael Schulz. Simultaneous graph embeddings with fixed edges. In F. V. Fomin, editor, 32nd Int. Workshop on Graph-Theoretical Concepts in Computer Science, volume 4271 of Lecture Notes in Computer Science, pages 325-335. Springer-Verlag, 2006.

Markus Geyer, Michael Kaufmann, and Imrich Vrt'o. Two trees which are self-intersecting when drawn simultaneously. In P. Healy and N. S. Nikolov, editors, 13th Int. Symp. on Graph Drawing, volume 3843 of Lecture Notes in Computer Science, pages 201-210. Springer-Verlag, 2006.

Emilio Di Giacomo and Giuseppe Liotta. A note on simultaneous embedding of planar graphs. In 21st European Workshop on Comp. Geometry, pages 207-210, 2005.