Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic.
Given k planar graphs G1,…,Gk, deciding whether they admit a simultaneous embedding with fixed edges (Sefe ) and whether they admit a simultaneous geometric embedding (Sge ) are NP-hard problems, for k≥3 and for k≥2, respectively. In this paper we consider the complexity of Sefe and of Sge when the graphs G1,…,Gk have a fixed planar embedding. In sharp contrast with the NP-hardness of Sefe for three non-embedded graphs, we show that Sefe is polynomial-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given k embedded planar graphs G1,…,Gk, deciding whether a Sefe of G1,…,Gk exists and deciding whether an Sge of G1,…,Gk exists are NP-hard problems, for k≥14 and k≥13, respectively.