Logo

Login | Create Account

An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing

Eiglsperger, Markus and Siebenhaller, Martin and Kaufmann, Michael (2004) An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing. [Conference Paper]

Full text not available from this repository.

Abstract

Sugiyama's algorithmic framework for layered graph drawing is commonly used in practical software. The extensive use of dummy vertices to break long edges between non-adjacent layers often leads to unsatisfactorial performance. The worst-case running-time of Sugiyamarsquos approach is O(|V||E|\log|E|) requiring O(|V||E|) memory, which makes it unusable for the visualization of large graphs. By a conceptually simple new technique we are able to keep the number of dummy vertices and edges linear in the size of the graph and hence reduce the worst-case time complexity of Sugiyamarsquos approach by an order of magnitude to O((|V|+|E|)\log|E|) requiring O(|V|+|E|) space. This work has partially been supported by the DFG-grant Ka512/8-2. It has been performed when the first author was with the Universität Tübingen.

Item Type:Conference Paper
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:582
Deposited By:Selbach, Anna
Deposited On:19 Jul 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=155

Repository Staff Only: item control page

References

1. D. Auber: Tulip - A Huge Graph Visualization Framework. In: Jünger, Mutzel (eds.): Graph Drawing Software, Springer-Verlag, pp. 105-126, 2003.

2. W. Barth, M. Jünger and P. Mutzel: Simple and Efficient Bilayer Cross Counting. In: Proceedings of Graph Drawing 2002, Springer LNCS 2528, pp. 130-141, 2002.

3. O. Bastert and C. Matuszewski: Layered drawings of digraphs. In: Kaufmann, Wagner (eds.): Drawing Graphs: Methods and Models, Springer LNCS 2025, pp. 104-139, 2001.

4. U. Brandes and B. Köpf: Fast and Simple Horizontal Coordinate Assignment. In: Proceedings of Graph Drawing 2001, Springer LNCS 2265, pp. 31-44. 2001.

5. E. Coffman and R. Graham: Optimal scheduling for two processor systems. Acta Informatica, 1: 200-213, 1972.

6. G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

7. P. Eades and D. Kelly: Heuristics for Reducing Crossings in 2-Layered Networks. Ars Combin., 21.A: 89-98, 1986.

8. P. Eades and N. Wormald: Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379-403, 1994.

9. A. Frick: Upper bounds on the number of hidden nodes in Sugiyama's algorithm. In: Proceedings of Graph Drawing 1996, Springer LNCS 1190, pp. 169-183, 1996.

10. E. Gansner, E. Koutsofios, S. North and K. Vo: A technique for drawing directed graphs. In: IEEE Transactions on Software Engineering, 19(3):214-229, 1993.

11. Graphviz - open source graph drawing software: http://www.research.att.com/sw/tools/graphviz/.

12. R. M. Karp: Reductibility among Combinatorial Problems. In: Miller R. E., Thatcher J. W. (eds.): Complexity of Computer Computations, Plenum Press, New York, pp. 85-103, 1972.

13. C. Matuszewski, R. Schönfeld and P. Molitor: Using sifting of k-layer straightline crossing minimization. In: Proceedings of the 7th Symposium on Graph Drawing (GD'99), Springer LNCS 2265, pp. 16-30, 2002.

14. N. Nikolov and P. Healy: How to layer a directed Acyclic Graph. In: Proceedings of the 9th Symposium on Graph Drawing (GD'01), Springer LNCS 2265, pp.16-30, 2002.

15. G. Sander: Graph layout through the VCG tool. In: Proceedings of Graph Drawing 1994, Springer LNCS 894, pp. 194-205, 1995.

16. D. Sleator and R. E. Tarjan: Self-Adjusting Binary Search Trees. In: Journal of the ACM, 3: 652-686, 1985.

17. K. Sugiyama, S. Tagawa and M. Toda: Methods for visual understanding of hierarchical system structures. In: IEEE Transactions on Systems, Man and Cybernetics, SMC-11(2): 109-125, 1981.

18. VCG - Visualization of Compiler Graphs: http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html.

19. V. Waddle and A. Malhotra: An E log E line crossing algorithm for levelled graphs. In: Proceedings of the 7th Symposium on Graph Drawing (GD'99), Springer LNCS 1731, pp.59-70, 1999.

20. yFiles - a Java Graph Layout and Visualization Library: http://www.yworks.com.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.