Extending ordered tree edit distance to DAGs
So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. The informal reasoning follows:


Edit distance between RNA structures with pseudoknots is Max-SNP hard and the reduction to Max-Cut works even if we ignore the RNA sequence (Ma, Wang &amp; Zhang, 2002: Computing similarity between RNA structures) 
One can represent an RNA structure with pseudoknots as a DAG with ordered children and labelled edges by extending the tree representation from Zhang &amp; Shasha 1989: Nodes still represent base pairs and unpaired nucleotides, "normal" edges represent the "is contained in" relationship and new type of  edges to represent a "contains only first nucleotide of a base-pair" relationship let us represent crossing base pairs.
An algorithm for edit distance on labelled DAGs would therefore likely give an algorithm for Max-Cut which is Max-SNP hard. This obviously depends on what edit operations are allowed, but it seems to work for any sensible set of edit operations I came up with.