Online Topological Ordering

of the nodes of a directed acyclic graph
while inserting $m$ edges can be solved
in $O(\min\{m^{3/2}\log n,m^{3/2}+n^2\log n\})$ time, an
improvement over the best known result of $O(mn)$.
In addition, we analyze the complexity of the same algorithm with
respect to the treewidth $k$ of the underlying undirected graph. We show
that the algorithm runs in time $O(mk\log^2 n)$ for general $k$ and
that it can be implemented to run in $O(n\log n)$ time on trees, which
is optimal. If the input contains cycles, the algorithm detects this.

This talk describes joint work with Hans Bodlaender. I will mention
several open problems.