Planar Graph Isomorphism

Question

In 1980, I. S. Filotti & Jack N. Mayer proved planar graph isomorphism testing could be done in polynomial time.

Does anyone have an implementation of that? I have a few billion planar graphs I'd like to sort through. Specifically, Gauss code loops can be used to enumerate self-crossing closed loops. My plan is to select the permutations that give planar graphs, then to group them by graph invariants to enumerate the unique closed loops.

Answer 1

If you are doing isomorphism testing, I'd recommend using nauty as an obvious choice. It is super fast, can find planar embeddings, and has the following quote on the webpage that suggests it may implement the algorithm you talk about:

"There are polynomial time algorithms for many special classes of graphs (bounded degree, bounded genus, classes with excluded minors or topological subgraphs). Few of these are practical, planar graphs being a notable exception."