Complexity of isotopy of embedded graphs I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous deformation of the plane tranforming one embedding to the other, without introducing any crossing between edges during the transformation.

This isotopy notion is stronger than the much studied isomorphism of (planar) graphs, for instance when a connected component is nested in another (the nesting is preserved by isotopy, not isomorphism).

Do we know anything about the complexity of this problem, or anything similar?

A similar question asks about how to define this isotopy notion in combinatorial terms:
Equivalent embeddings of a graph

Precision: I am primarily interested in the case where the embedded graph is not connected.
Since you only care about embeddings in the plane, and every oriented homeomorphism of the plane is isotopic to the identity (Alexander's trick), testing whether two embedded graphs are isotopic is equivalent to testing whether they are congruent by an oriented homeomorphism. And this is a purely combinatorial notion: for example it is equivalent to the two graphs having the same (extended) combinatorial maps (Lemma 5 in our paper with Eric that you cited in your answer).

Testing whether two embedded graphs have the same combinatorial map is solvable in linear time according to this paper but I have never found the full version, and for planar maps it is actually quite simple.

If you already have the isomorphism between the graphs, this is easily doable in linear time (just check that the combinatorics agree everywhere). If you don't, you need to find it. Luckily, planar graph isomorphism is easy and doable in linear time (Hopcrof-Wong). 

Now that does not solve your problem exactly, because maybe this could find a graph isomorphism that is not a map isomorphism, while another graph isomorphism would be. But this is not a real issue: the disconnected components are arranged in a tree-like fashion due to the nesting, and thus can be encoded with a tree. Similarly, bi-connected components are arranged in a tree (the block-cut tree), and so are tri-connected components (the SPQR tree). And tri-connected components have a unique embedding, and thus are map-isomorphic if and only if they are graph-isomorphic. (some care needs to be taken (e.g. ordering and/or labeling) so that these trees precisely encode the map you are looking at).

So mixing the Hopcroft-Wong algorithm with some tree isomorphism algorithm should solve your problem in linear time. (this is actually similar to the planar graph isomorphism algorithm, see for example Hopcroft-Tarjan)