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 , pp. 280-290(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item