Upper bounds on the number of hidden nodes in the Sugiyama algorithm

The Sugiyama algorithm is a well-known techique for drawing arbitrary directed grapds G=(V,E). It is being widely used in current graph-drawing systems. Despite its importance and wide-spread use, little is known about the time and space complexity of several parts of the algorithm. This paper improves this situation by analyzing the exact and asymptotic worst-case complexity of the simplification phase of the Sugiyama algorithm. This complexity is dominated by the number d of added invisible (a.k.a. hidden or dummy) nodes. The best previously known upper bound for this number is O(min{|V|^3,|E|^2}). We connect both partial results and show that d can be expressed a function d(h,n,m) of the height h of the underlying layering, the number of vertices n=|V| and the number of edgeds |E|. We analyze d(h,n,m) and improve on the previously known bounds by giving a closed-form description and sharp asymptotic bounds for several relevant cases