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, Sydney, Australia , 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
ID Code:844

Repository Staff Only: item control page


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

C. Collberg, S. G. Kobourov, J. Nagra, J. Pitts, and K. Wampler. A system for graph-based visualization of the evoltion of software. In SoftVis, pages 377-86, 2003.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

E. Di Giacomo and G. Liotta. A note on simultaneous embedding of planar graphs. In EWCG, pages 207-210, 2005.

C. Erten and S. G. Kobourov. Simultaneous embedding of planar graphs with few bends. In GD, pages 195-205, 2004.

F. Frati. Embedding graphs simultaneously with fixed edges. In GD, pages 108-113. Lecture Notes in Computer Science, 2006.

F. Frati, M. Kaufmann, and S. Kobourov. Constrained simultaneous and near-simultaneous embeddings. Tech. Report RT-DIA-120-2007, University of Roma Tre,, 2007.

M. Geyer, M. Kaufmann, and I. Vrto. Two trees which are self-intersecting when drawn simultaneously. In GD, pages 201-210, 2005.

P. Healy, A. Kuusik, and S. Leipert. A chracterization of level planar graphs. Discr. Math., 280(1-3):51-63, 2004.

M. Jünger and S. Leipert. Level planar embedding in linear time. Jour. of Graph Alg. and Appl., 6(1):67-113, 2002.

M. Kaufmann and D. Wagner, editors. Drawing Graphs, Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer, 2001.