Gustavo Lacerda

As a theoretician it pains me to do this, but there are some decent algorithms out there for testing graph isomorphism and reducing to a canonical graph. In a previous life, when I was doing combinatorial design theory, I used Brendan McKay's nauty, which does exactly what you asked for -- given a graph, it returns a representation that is canonical up to isomorphism. I have no idea what algorithm it uses, but it was reasonably fast when I used it 7 or 8 years ago.