Complexity of isotopy of embedded graphs

Question

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.

Answer 1

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)

Answer 2

(All of the below is assuming your graphs are connected.)

Every isotopy class of graphs with $e$ edges embedded in the sphere (which is almost the plane) corresponds to a pair of permutations $\sigma,\tau$ on $2e$ letters which satisfy $(\sigma\tau)^2 = 1$, and $\sigma,\tau$ are determined up to simultaneous conjugacy (the dual graph corresponds to the pair $\tau^{-1},\sigma^{-1}$). The correspondence is explicit:

First, label each side of each edge of your graph with a number from $1$ to $2e$ in any way you please. To define $\tau$, we make a cycle for each vertex $v$, which involves only what $v$ sees as the "right hand sides" of each edge meeting $v$ (ok, fine, the clockwise sides), and rotates each one one step counterclockwise. To define $\sigma$, we make a cycle for each face $f$, which rotates all of the edge labels that $f$ meets (which face $f$) one step counterclockwise (from $f$'s point of view - so, for the infinite face, you rotate clockwise from the view inside the graph). If you've done that all correctly, then $\sigma\tau$ should be the involution that swaps the two sides of each edge. As an example, if my graph is a square, then I might get $\sigma = (1\; 2\; 3\; 4)(5\; 6\; 7\; 8)$, $\tau = (1\; 8)(2\; 7)(3\; 6)(4\; 5)$, $\sigma\tau = (1\; 5)(2\; 8)(3\; 7)(4\; 6)$.

From the permutations $\sigma,\tau$, we can reconstruct the isotopy class by gluing together the faces, edges, and vertices according to the permutations, and being pleasantly surprised when the resulting surface comes out as a sphere.

Since the way we labeled the sides of the edges was arbitrary, if we pick any permutation $s$ of the $2e$ labels, then the pair of permutations $s\sigma s^{-1},s\tau s^{-1}$ describes the same isotopy class. So if one of your graphs is described by a pair $\sigma,\tau$ and the other is described by a pair $\sigma',\tau'$, then we have to determine if there is an $s$ such that $s\sigma s^{-1} = \sigma', s\tau s^{-1} = \tau'$, and which sends the outside face to the outside face. This is significantly easier to test than it sounds: if we correctly guess the value of $s(1)$, then we can fill in all of the other values of $s$ very rapidly. If we know the value of $s(i)$, then we have $s(\sigma(i)) = \sigma'(s(i))$ and $s(\tau(i)) = \tau'(s(i))$, and since our graphs are connected, $\sigma$ and $\tau$ generate a transitive group, so this eventually determines every $s(i)$ from $s(1)$.

Answer 3

The closest I could find so far is Eric Colin de Verdière and Arnaud de Mesmay 's work:

• Testing Graph Isotopy on Surfaces, Éric Colin de Verdière and Arnaud de Mesmay arxiv:1310.2745
• Computational topology of graphs on surfaces, Éric Colin de Verdière arxiv:1702.05358

However the cases studied here assume that the input data consists in two embeddings of the same graph: we are already provided with a correspondence between the embedded edges and vertices, which probably makes the problem significantly easier.