Canonical labeling of special classes of DAGs Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.


  What are some special classes of DAGs that can be canonized in polynomial time ?
To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and polytrees, as an orientation-labeled variant of trees.

On the other hand, it's tempting to list multitrees (as I did in an earlier incorrect version of this answer), using canonization of trees to prioritize their topological orderings, but they're GI-complete (subdivide each edge of an undirected graph into two directed edges oriented outwards from the subdivision point), so that doesn't work.