Article

Graph Layout for Displaying Data Structures

Author:

Vance E. WaddleAuthors Info & Claims

GD '00: Proceedings of the 8th International Symposium on Graph Drawing

Pages 241 - 252

Published: 20 September 2000 Publication History

Abstract

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.

References

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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.

[7]

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

[8]

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

[9]

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.

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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.

[19]

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

[20]

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.

[21]

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.

[22]

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

[23]

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.

[24]

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

[25]

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

Cited By

Cortese PDi Battista GMoneta APatrignani MPizzonia M(2006)Topographic Visualization of Prefix Propagation in the InternetIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.18512:5(725-732)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.185
Forster M(2004)A fast and simple heuristic for constrained two-level crossing reductionProceedings of the 12th international conference on Graph Drawing10.1007/978-3-540-31843-9_22(206-216)Online publication date: 29-Sep-2004
https://dl.acm.org/doi/10.1007/978-3-540-31843-9_22
Purchase HMcGill MColpoys LCarrington DEades PPattison T(2001)Graph drawing aesthetics and the comprehension of UML class diagramsProceedings of the 2001 Asia-Pacific symposium on Information visualisation - Volume 910.5555/564040.564056(129-137)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.5555/564040.564056

Graph Layout for Displaying Data Structures

Recommendations

Queue Layout of Bipartite Graph Subdivisions

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmović and D. R. Wood showed that for every ...
Interactive graph layout: the exploration of large graphs
(d+1,2) -Track Layout of Bipartite Graph Subdivisions

A ( k ,2- track layout of a graph G consists of a 2- track assignment of G and an edge k -coloring of G with no monochromatic X-crossing . This paper studies the problem of ( k ,2)-track layout of bipartite graph subdivisions. Recently V.Dujmović and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GD '00: Proceedings of the 8th International Symposium on Graph Drawing

September 2000

417 pages

ISBN:3540415548

Editor:
Joe Marks

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 September 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cortese PDi Battista GMoneta APatrignani MPizzonia M(2006)Topographic Visualization of Prefix Propagation in the InternetIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.18512:5(725-732)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.185
Forster M(2004)A fast and simple heuristic for constrained two-level crossing reductionProceedings of the 12th international conference on Graph Drawing10.1007/978-3-540-31843-9_22(206-216)Online publication date: 29-Sep-2004
https://dl.acm.org/doi/10.1007/978-3-540-31843-9_22
Purchase HMcGill MColpoys LCarrington DEades PPattison T(2001)Graph drawing aesthetics and the comprehension of UML class diagramsProceedings of the 2001 Asia-Pacific symposium on Information visualisation - Volume 910.5555/564040.564056(129-137)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.5555/564040.564056

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents