Complexity of isotopy of embedded graphs
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)