Maintaining a topological order under edge insertions

A topological order of the vertices of a directed acyclic graph G = (V,E) is any total order ord such that if (x, y) is an element of E, then x precedes y in ord. In this paper we consider the dynamic version of this problem, and provide simple algorithms and data structures achieving O(n) amortized time per edge insertion starting from an empty graph, which favorably compares to the trivial O(m+n) time bound per operation obtained applying the off-line algorithm. The additional space requirement, beside the representation of the graph itself, is O(n). Experimental results show that our algorithm performs in practice orders of magnitude faster than the off-line algorithm.