Graph Isomorphisms

Two graphs are isomorphic if there is a renaming of vertices that makes them equal. In other words, if you are given two different drawings (or embeddings as nerds are apt to say) of the same graph, you can always deform one into the other.

    Pairs of Isomorphic Graphs

Determining if two graphs are isomorphic is a mysterious problem, in that it is conjectured to lie somewhere in the space between NP-complete and P, possibly separating them, and thus deciding P vs NP.  Now, for planar graphs a polynomial algorithm is known (Hopcroft 1973) when the maximum degree is bounded by a constant. In some sense, the graph isomorphism problem is easy except for a tiny sliver set of irreducibly complex graphs, and these pathological subsets are what make graph problems difficult.

Recently, Laszlo Babai at the University of Chicago has claimed an astounding theorem, that the Graph Isomorphism problem can be solved in quasipolynomial time. He didn’t get a polynomial time algorithm, but he got something quite close, which is exciting!