Online transitive closure better than O(N^2) per edge addition
O(n) time per edge addition:


G. F. Italiano (1986): Amortized efficiency of a path retrieval data structure, Theoretical Computer Science 48, 273–281.
J. A. La Poutré and J. van Leeuwen (1988): Maintenance of transitive closures and transitive reductions of graphs, Proc. WG 1987.