Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
What does it mean to find them? It seems like there could be exponentially many. –  Qiaochu Yuan Aug 27 '13 at 6:48
    
Isn't it just the problem of finding the automorphisms of a graph? You can check whether they are isomorphic, and then every other isomorphism is the first isomorphism plus an automorphism. Also if G is a star, there are $(n-1)!$ automorphisms, so we can not list them in polynomial time. –  Daniel Soltész Aug 27 '13 at 7:10
    
Do you mean all graph isomorphisms? Or only isomorphisms that keep the order of half-edges around each node in the planar embedding? Maybe there can't be more than polynomial many of the latter ones, at least with some connectivity constraint. –  Zsbán Ambrus Aug 27 '13 at 8:02
1  
Planar graphs are not 'rigid' enough to allow a polynomial time algorithm; however if there would be a further restriction to planar graphs that correspond to the edges of a 3D polyhedron with the restriction that every edge is adjacent to exactly two distinct faces and every vertex is adjacent to at least three distinct faces, things should be different: there are only polynomially many pairs of faces from both graphs, which can be aligned in only polynomially many orientations, for which it has to be checked whether an isomorphism has been detected. –  Manfred Weis Aug 27 '13 at 8:03
    
b.t.w. the usual term for 'finding' is 'reporting' in contrast to 'counting', if one is only interested in knowing how many there are. –  Manfred Weis Aug 27 '13 at 8:07
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.