In Orderly algorithms for generating restricted classes of graphs, Colbourn and Read expand on the earlier introduction of the orderly generation of graphs.
Briefly, orderly generation allows you to exhaustively generate all non-isomorphic graphs on p vertices, by augmenting the canonical set of (p, q) graphs (with q edges) with all possible new edges: leading to a new set of (p, q + 1) graphs. Each generated graph must be checked to ensure it is canonical before it is added to the (p, q + 1) list.
Colbourn and Read state:
The importance of the orderly methods is that, unlike classical methods, they do not search through the graphs already in (p, q + 1) to determine if the graph being produced is a duplicate.
What I'm confused about is that their method already requires an "is canonical?" check. If that check is as difficult as simply creating the canonical labeling of the graph, then it seems the method doesn't provide much advantage, since you could simply generate the canonical representation of the graph and determine if it has already been generated (e.g., via a simple dictionary lookup).
So it seems that this approach saves computation in the case that the cost to check "Is this graph canonical?" is of a smaller order than "Compute the canonical form of this graph." Is that the case in general? For restricted cases of graphs?
Even if that were not the case, the approach is still useful since it doesn't require the dictionary lookup in a potentially large set of generated graphs, but that seems much less interesting that if it actually resulted in a cheaper (order-wise) generation of graphs.