Given a graph in which we can insert vertices and edges, and we can also remove them. Before finishing the edge insertion operation, I would like to check whether the graph would still be acyclic if I added that new edge, and cancel the operation if not.
I can easily check whether the graph is acyclic at each operation in O(n) time using a simple depth first search. However this will not scale well for extremely large graphs.
I was wondering whether we could maintain some additional information in the vertices / edges, so that there is an asymptotically faster way to detect whether the graph would become cyclic. E.g. I could do an O(log(n)) operation at each graph mutating operation, and maintain some information that magically make my acyclicity check faster, kind of how balanced binary search trees make it possible to always query the smallest element in O(log(n)) time.
It seems that there is a long line of research on this problem. The magic phrase is "incremental cycle detection". The newest paper I could find is this; it contains a large number of references to earlier papers.
The gist of it is that there are algorithms for doing this in sublinear time (e.g., on the order of $\sqrt{n}$ times something polylogarithmic per update), but according to the authors of the linked paper "we are far away from designing an algorithm that has polylogarithmic update time". The best algorithm also depends on whether the input graphs are sparse or dense, and whether you are happy with a randomized algorithm. Implementing some of these algorithms seems to be non-trivial but not hopeless. If you want to try, this looks like a nice choice.