  We investigate the following problem: Given two embeddings G_1 and G_2 of the
same abstract graph G on an orientable surface S, decide whether G_1 and G_2
are isotopic; in other words, whether there exists a continuous family of
embeddings between G_1 and G_2. We provide efficient algorithms to solve this
problem in two models. In the first model, the input consists of the
arrangement of G_1 (resp., G_2) with a fixed graph cellularly embedded on S;
our algorithm is linear in the input complexity, and thus, optimal. In the
second model, G_1 and G_2 are piecewise-linear embeddings in the plane minus a
finite set of points; our algorithm runs in O(n^{3/2}\log n) time, where n is
the complexity of the input. The graph isotopy problem is a natural variation
of the homotopy problem for closed curves on surfaces and on the punctured
plane, for which algorithms have been given by various authors; we use some of
these algorithms as a subroutine. As a by-product, we reprove the following
mathematical characterization, first observed by Ladegaillerie (1984): Two
graph embeddings are isotopic if and only if they are homotopic and congruent
by an oriented homeomorphism.
