1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ What does it mean to find them? It seems like there could be exponentially many. $\endgroup$ Aug 27, 2013 at 6:48
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2013 at 7:10
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2013 at 8:02
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 27, 2013 at 8:03
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 27, 2013 at 8:07

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Actually, the question was about the generation of all isomorphisms, not about a system of generators. So it is absolutely not clear whether the original author is “missing the point”, too, or whether your contribution is orthogonal to the intention of the original author. $\endgroup$ Jul 20, 2019 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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