Find all the isomorphisms between two planar graphs

Question

Since planar graph isomorphic problem can be solved in polynomial, can we find all isomorphisms between two planar graphs in polynomial time?

Answer 1

As the comments point out there is no general algorithm to enumerate possibly exponentially many isomorphisms.

Nevertheless, you can enumerate the isomorphisms in polynomial delay, which means that the time spent between two outputs is polynomial in the size of the graph.

A rough estimation can be done using the following algorithm to find all isomorphisms from graph $A$ to graph $B$:

Preparation:

Enumerate all nodes with numbers from $1$ to $n$ and assign for each node a Graph $G_i$ that is a circle with $n+1$ nodes and has $i$ spikes (additional nodes that are directly connected to the circle. Thus these graphs $G_i$ are paiwise nonisomorphic. For each $G_i$ mark a connecting node. We mark a node in graph $A$ or $B$ by connecting this node to the connecting node of $G_i$. As we use two copies of $G_i$ (one for $A$ and one for $B$) we denote them with $G_i^A$ and $G_i^B$. If every node of $A$ is marked by a distinct graph $G_i^A$ and every node of $B$ is marked by a distinct graph $G_i^B$ these graphs are planar as $G_i^J$ is planar and connected by only one edge. Each of these graphs has $O(n^2)$ nodes. Thus, checking if they are isomorphic is polynomial in the size of $A$.

Enumeration:

Find_Isomorphism(i) {
   mark node $a_i$ with graph $G_i^A$
   for j in 1, ... , n {
     if node $b_j$ is 
     mark node $b_j$ with graph $G_i^B$
     if marked graphs $A$ and $B$ are isomorphic {
       if (i = n) {
         Output_Isomorphism
       } else {
         Find_Isomorphism(i+1)
       }
     }
     unmark node $b_j$
   }
}

The isomorphism is encoded by the permutation of the marker graphs $G_i$.

The procedure Find_Isomorphism goes into recursion only, if the marked graphs are still isomorphic. Thus, an isomorphism is found whenever the largest depth of recursion is reached. At each level of recursion at most $n$ graph isomorphy tests are performed. As we have $n$ levels, the delay between the outputs of two isomorphisms is about $O(n^2)$ times the complexity of the graph isomorphism problem of the marked graph, which is polynomial as shown above.

Note: There are much more effective ways of marking the nodes than in this example.

Edit: It is easy to see that a polynomial delay algorithm is polynomial iff its output is polynomial.

Answer 2

If $\psi$ is a fixed isomorphism from a graph $G$ to a graph $H$, then each isomorphism from $G$ to $H$ is the composition of $\psi$ with an element of $\mathrm{Aut}(H)$. So I can specify the set of isomorphisms from $G$ to $H$ by giving $\psi$ and a set of generators for $\mathrm{Aut}(H)$.

So the comments about "exponentially many isomorphisms" seem to be missing the point. Given a polynomial time algorithm for computing the automorphism group of a planar graph, we can produce an isomorphism and set of generators in polynomial time.