<p>To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and <a href="https://en.wikipedia.org/wiki/Polytree" rel="nofollow">polytrees</a>, as an orientation-labeled variant of trees.</p>

<p>On the other hand, it's tempting to list <a href="https://en.wikipedia.org/wiki/Multitree" rel="nofollow">multitrees</a> (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.</p>

CC BY-SA 3.0
2013-03-30T16:25:45.663Z
Thanks David. Hamiltonian-DAGs and orientations of trees are two classes that occurred to me. Is this the state-of-the art ? What about planar DAGs, DAGs with limited number of source/sinks ? Are they GI-complete ?
Shiva Kintali
CC BY-SA 3.0
2013-03-30T22:52:49.100Z
I imagine planar DAGs are not any harder than other kinds of planar graphs to solve isomorphism for (logspace, and therefore P). The limited number of sources and sinks doesn't help, though, because you could just add a new source or sink to your graph connecting to all the vertices that were previously sources or sinks, reducing the number of sources or sinks to one without making the problem easier.
David Eppstein
CC BY-SA 3.0
2013-03-29T17:27:04.943Z
2013-03-29T23:29:02.833Z
2013-03-29T23:29:02.833Z
David Eppstein
<p><a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem">Graph Isomorphism</a> of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.</p>

<blockquote>
  <p>What are some special classes of DAGs that can be canonized in polynomial time ?</p>
</blockquote>

<ds.algorithms><graph-theory><co.combinatorics><graph-isomorphism><directed-acyclic-graph>
Canonical labeling of special classes of DAGs
Shiva Kintali
# Canonical labeling of special classes of DAGs

(Asked by: username_0 on 2013-03-29)

[Graph Isomorphism](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) 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 ?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, graph-isomorphism, directed-acyclic-graph


---

## 1 answers

### Answer by username_1 on 2013-03-29. Score: 6 | Accepted answer

To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and [polytrees](https://en.wikipedia.org/wiki/Polytree), as an orientation-labeled variant of trees.

On the other hand, it's tempting to list [multitrees](https://en.wikipedia.org/wiki/Multitree) (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.

> **Comments:**
> **username_0**: Thanks David. Hamiltonian-DAGs and orientations of trees are two classes that occurred to me. Is this the state-of-the art ? What about planar DAGs, DAGs with limited number of source/sinks ? Are they GI-complete ?  
> **username_1**: I imagine planar DAGs are not any harder than other kinds of planar graphs to solve isomorphism for (logspace, and therefore P). The limited number of sources and sinks doesn't help, though, because you could just add a new source or sink to your graph connecting to all the vertices that were previously sources or sinks, reducing the number of sources or sinks to one without making the problem easier.  

---

