Algorithm to determine isomorphism of 2 maximal planar graphs

Question

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem to find any understandable description of such algorithms. Could anyone point me to a book or website that explains it (preferably for mere mortals). In addition to that, is there an algorithm that can compute a "string" for (maximal) planar graphs such that two isomorphic graphs get the same string ? Tx.

Answer 1

You didn't say whether your interest is theoretical or practical. If it is theoretical, note that maximal planar graphs can be tested in linear time. See the paper of Hopcroft and Wong mentioned in the Kuluk et al. paper the Igor provided. I've never been satisfied by that paper, but others have cleaned it up since (was it Mohar? I don't remember.)

From a practical point of view, I'll assume you already embedded the graphs on the sphere (so you have a cyclic order at each vertex). There is a string associated with each flag (vertex, edge on that vertex, side of that edge) which you can make by scanning the graph starting at that flag. Any of the standard scans like DFS or BFS can be used. When the scan algorithm asks you to examine the neighbours of a vertex, do that in embedding order starting with the parent vertex (or with the flag, in the case of the first vertex). Now turn a history of the scan into a string. Number each vertex as you discover it, and list the edges as you meet them, using the new numbers. When the scan is done, you have a string associated with that flag.

Naively you can make a string for each flag and take the string representing the graph to be the lexicographically greatest such string. This is clearly an $O(n^2)$ algorithm. To do (much) better in practice, restrict which flags you start scans at using combinatorial invariants. For example, you could consider just flags starting at a vertex of maximum degree and ending at a neighbour of the least degree. If there is more than one such flag, try a more complex invariant (say, distinguish vertices of the same degree by looking at the degrees of their neighbours). Then perform scans starting only at the flags remaining. There is a trade-off between the time taken to reduce the number of scans and the time saved by doing fewer scans.

You can also try comparing each string to the greatest string you saw so far during each scan, as this will often allow scans to be aborted early. This is the method used in plantri.

A side-benefit of this approach is that you get a list of all the automorphisms: each string which is the same as the best string provides one.

With these improvements, the time will be still be $\Omega(n^2)$ in the worse case, but the worst case will be extremely rare. If you are processing large files of graphs, you will have trouble distinguishing the performance from linear (assuming you are careful with your implementation).

Answer 2

Grohe and Marx developed a polynomial time algorithm for isomorphism testing in a graph class defined by an excluded subdivision (paper), which implies and is a vast generalisation of the result for planar graphs and the result for bounded degree graphs.

Answer 3

The paper of Kuluk, Holder, Cook does what you want (it is $O(n^2)$ time). If by maximal planar graph you mean a triangulation of the sphere, than the problem is much easier: you embed the graph in the sphere (this can be done in linear time, and the algorithm is simple, see the celebrated:

MR1010382 (91b:06008) Reviewed 
Schnyder, Walter(1-LAS)
Planar graphs and poset dimension. 
Order 5 (1989), no. 4, 323–343. 
06A07 (05C10 05C75) 

The structure representing this embedding is simply the adjacency matrix of the graph with the cyclic order around each vertex. Now, a theorem of Whitney states that the planer embedding is unique (except for flipping the graph over). The algorithm should now be obvious (though it is slightly less clear how to produce the string you seek).