Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00194
Constrained Simultaneous and NearSimultaneous Embeddings
Vol. 13, no. 3, pp. 447465, 2009. Regular paper.
Abstract 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 γ:V_{1} → V_{2} is a pair of planar straightline drawings Γ_{1} of G_{1} and Γ_{2} of G_{2}, such that each vertex
v_{2}=γ(v_{1}), with v_{1} ∈ V_{1} and v_{2} ∈ V_{2}, is mapped in Γ_{2} to the same point where v_{1} is mapped in Γ_{1}.
In this paper we examine several constrained versions and a relaxed version of the geometric simultaneous embedding problem. We show that assuming
that the input graphs do not share common edges does not yield larger 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 in the standard geometric
simultaneous embedding setting. Finally, we present some results on the nearsimultaneous embedding problem, in which vertices are not forced to be
placed exactly at the same, but just at "nearby" points in different drawings.

Submitted: December 2007.
Reviewed: May 2008.
Revised: August 2008.
Accepted: November 2008.
Final: December 2008.
Published: November 2009.
