Graph Layout for Displaying Data Structures

Waddle, Vance (2001) Graph Layout for Displaying Data Structures. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 241-252 (Official URL:

Full text not available from this repository.


Displaying a program's data structures as a graph is a valuable addition to debuggers, however, previous papers have not discussed the layout issues specific to displaying data structures. We find that the semantics of data structures may require constraining node and edge path orderings, and that nonhierarchical, leveled graphs are the preferred data structure display. We describe layout problems for data structures, and extend the Sugiyama algorithm to solve them.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_23
Classifications:M Methods > M.500 Layered
J Applications > J.999 Others
P Styles > P.480 Layered
ID Code:366

Repository Staff Only: item control page


K.-F. Boehringer, and F. N. Paulisch Using Constraints to Achieve Stability in Automatic Graph Layout Algorithms, ACM CHI '90 Proceedings, pp. 43-51.

A. Borning, The Programming Language Aspects of ThingLap, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems, 3(4), pp. 252-387, 1981.

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

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

P. Eades, W. Lai, K. Misue, and K. Sugiyama, Preserving the Mental Map of a Diagram, Proceedings Compugraphics '91, pp. 24-33, 1991.

E.R. Gansner, E. Koutsofios, S.C. North and K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, Vol. 19, No. 3. 1993.

W. He and K. Marriott, Constrained Graph Layout, Proceedings of Graph Drawing GD'96, pp. 217-232, Springer, 1996.

T. Kamps, J. Kleinz, and J. Read, Constraint-Based Spring Model for Graph Layout, Proceedings of Graph Drawing GD '95, pp. 349-360, Springer.

C. Kosak, J. Marks, and S. Shieber, Automating the Layout of Network Diagrams with Specified Visual Organization, IEEE Transactions on Systems, Man and Cybernetics, Vol. 24, No. 3, pp. 440-454.

D. E. Knuth, The Art of Computer Programming, Vol 1: Fundamental Algorithms, Second Edition, Addison-Wesley, 1973.

D. E. Knuth, The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley, 1973.

J. Korn, A. W. Appel, Traversal-based Visualization of Data Structures, IEEE Symposium on Information Visualization (Info Vis '98), pp. 11-18.

B. Myers, INCENSE: A System for Displaying Data Structures, Proc. SIGGRAPH 1983, pp. 115-125.

S.C. North, Incremental Layout in DynaDAG, Proc. of Graph Drawing GD '95, pp. 409-418, Springer.

S.C. North and E. Koutsofios, Applications of Graph Visualization, Graphics Interface '94, pp. 235-245.

S.P. Reiss, The Field Programming Environment: A Friendly Integrated Environment for Learning and Development, Kluwer, 1995.

K. Ryall, J. Marks, and S. Shieber, An Interactive System for Drawing Graphs, Proc. Graph Drawing GD '96, pp. 387-393, Springer.

Jochem Seeman, Extending the Sugiyama Algorithm for Drawing UML Class Diagrams: Towards Automatic Layout of Object-Oriented Software Diagrams, pp. 415-427, Proc. Graph Drawing '97, Giuseppe DiBattista, ed. Springer.

T. Shimomura and S. Isoda, Linked-List Visualization for Debugging, IEEE Software, Vol. 8, No. 3, pp. 44-51, May 1991.

Sugiyama, K., Tagawa, S., and M. Toda, Methods for Visual Understanding of Hierarchical Structures, IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-11, No. 2. Feb. 1981.

K. Sugiyama and K. Misue, Visualization of Structural Information: Automatic Drawing of Compound Digraphs, IEEE Transactions on Systems, Man, and Cybernetics, Vol 21, No. 4, pp. 876-892, July/August, 1991.

V. Waddle, A Sugiyama-Style Layout Algorithm for Nonhierarchical, Leveled Graphs, in preparation.

V. Waddle, and A. Malhotra, An E log E Line Crossing Algorithm for Leveled Graphs, Proc. of Graph Draw GD '99, pp. 59-71, Springer.

J. Yang, C.A. Shaffer, and L. S. Heath, SWAN: A Data Structure Visualization System, Proc. of Graph Drawing GD '95, pp 520-523.

A. Zeller and D. Luetkeaus, DDD - A Free Graphical Front-end for UNIX Debuggers, SIGPLAN Notices, 31(1):22-27, January 1996.