Constrained Simultaneous and Near-Simultaneous Embeddings

Frati, Fabrizio and Kaufmann, Michael and Kobourov, Stephen G. (2008) Constrained Simultaneous and Near-Simultaneous Embeddings. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 268-279(Official URL:

Full text not available from this repository.


A geometric simultaneous embedding of two graphs G_1=(V_1,E_1) and G_2=(V_2,E_2) with a bijective mapping of their vertex sets gamma : V_1 rightarrow V_2 is a pair of planar straight-line drawings Gamma _1 of G_1 and Gamma _2 of G_2, such that each vertex v_2=gamma(v_1) is mapped in Gamma _2 to the same point where v_1 is mapped in Gamma _1, where v_1 in V_1 and v_2 in V_2. In this paper we examine several constrained versions and a relaxed version of the geometric simultaneous embedding problem. We show that if the input graphs are assumed to share no common edges this does not seem to yield large classes of graphs that can be simultaneously embedded. Further, if a prescribed combinatorial embedding for each input graph must be preserved, then we can answer some of the problems that are still open for geometric simultaneous embedding. Finally, we present some positive and negative results on the near-simultaneous embedding problem, in which vertices are not mapped exactly to the same but to "near" points in the different drawings.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_27
Classifications: G Algorithms and Complexity > G.490 Embeddings

Actions (login required)

View Item View Item