  We investigate algorithms for canonical labelling of site graphs, i.e. graphs
in which edges bind vertices on sites with locally unique names. We first show
that the problem of canonical labelling of site graphs reduces to the problem
of canonical labelling of graphs with edge colourings. We then present two
canonical labelling algorithms based on edge enumeration, and a third based on
an extension of Hopcroft's partition refinement algorithm. All run in quadratic
worst case time individually. However, one of the edge enumeration algorithms
runs in sub-quadratic time for graphs with "many" automorphisms, and the
partition refinement algorithm runs in sub-quadratic time for graphs with "few"
bisimulation equivalences. This suite of algorithms was chosen based on the
expectation that graphs fall in one of those two categories. If that is the
case, a combined algorithm runs in sub-quadratic worst case time. Whether this
expectation is reasonable remains an interesting open problem.
