Upper Bounds on the Number of Hidden Nodes in Sugiyama's Algorithm

Frick, Arne (1997) Upper Bounds on the Number of Hidden Nodes in Sugiyama's Algorithm. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 169-183 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_46).

Full text not available from this repository.


This paper analyzes the exact and asymptotic worst-case complexity of the simplification phase of Sugiyama's algorithm for drawing arbitrary directed graphs. The complexity of this phase is determinatedby the number of hidden nodes inserted. The best previously known upper bound for this number is O(max{|V|³, |E|²}). This paper establishes a relation between both partial results and gives upper bounds for many classes of graphs. This is archived by constructing a worst-case example for every legal configuration C=(h,n,m) of the input hierarchy for the simplification phase. These results provide further insight into the worst-case runtime and space complexity of Sugiyama's algorithm. Possible applications include their use as feasibility criteria, based on simpy derived quantitative information on the graph.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_46
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
P Styles > P.480 Layered
ID Code:116

Repository Staff Only: item control page


G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Report, June 1993.

P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information Processing, 14(4):424-437, 1990.

M. Fröhlich and M. Werner. Demonstration of the interactive graph visualization system davinci. In Tamassia and Tollis [13].

E.R. Gansner, E. Koutsofios, S.C. North, and K. P. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19:214-230, 1993.

F. Harry. Graph Theorie. Series in Mathematics. Addison Wesley Publishing Company, 1969.

M. Himsolt. GraphEd: a graphical platform for the implementation of graph algorithms. In Tamassia and Tollis [13].

I. Lemke. Entwicklung und implementierung eines visualisierungswerkzeuges für anwendungen in übersetzerbau. Diplomarbeit, Universität des Saarlandes, Institut für Informatik, 1994.

Brendan Madden, Patrick Madden, Steve Powers, and Michael Himsolt. Portable graph layout and editing. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 385-395. Springer-Verlag, 1996.

F. Newbery-Paulisch and W.F. Tichy. Edge: An extendible graph editor. Softw. - Pract. Exp., 20(S1):S1/63-S1/88, June1990.

G. Sander. Graph layout through the VCG tool. In Tamassia and Tollis [13].

G. Sander. Visualisierungstechniken für den Compilerbau. PhD thesis, Univ. des Saarlandes, FB 14 Informatik, saarbrücken, 1996.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.

Roberto Tamassia and Ioannis Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of LNCS, pages 416-427. DIMACS Workshop on GD, Springer-Verlag, 1995.

Waterloo Maple Software. Maple V Release3, 1994.