Re: Dynamic cycle Detection

I am working on a problem in which I add edges to a DAG G one by one.
After each addition I need to check if the addition made the digraph
cyclic.

Keywords: "online cycle detection", "dynamic cycle detection".
There is literature on this subject; do a literature search, and
you'll find prior work. (See, e.g., Schmueli, 1983.)

Also, here is a paper that uses online cycle detection and elimination
in an application, and discusses a heuristic technique that seems to
work well in that application:
http://theory.stanford.edu/~aiken/publications/papers/pldi98b.ps
.