Is there a data structure for DAGs that supports efficient edits?

Question

I'm looking for a data structure that will store any DAG, but can efficiently (i.e., sub-linearly in the number of edges/vertices) detect if adding an edge would create a cycle (and thus prevent you from breaking the acyclic invariant). Does anyone know of such a thing?

Thanks!

Answer 1

You could maintain a datastructure about the graph's transitive closure. Then checking whether adding an edge causes cycles is done in constant time; if you want to add edge (i,j), check if there is already a path from j to i. However, updating the datastructure could be more costly in general (see e.g. La Poutré and van Leeuwen).