Constrained Simultaneous and Near-Simultaneous Embeddings

Abstract

A geometric simultaneous embedding of two graphs G₁=(V₁,E₁) and G₂=(V₂,E₂) with a bijective mapping of their vertex sets γ:V₁ → V₂ is a pair of planar straight-line drawings Γ₁ of G₁ and Γ₂ of G₂, such that each vertex v₂=γ(v₁), with v₁ ∈ V₁ and v₂ ∈ V₂, is mapped in Γ₂ to the same point where v₁ is mapped in Γ₁. 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 near-simultaneous embedding problem, in which vertices are not forced to be placed exactly at the same, but just at "nearby" points in different drawings.