Reduction of Visual Complexity in Dynamic Graphs

Kimelman, Doug and Leban, Bruce and Roth, Tova and Zernik, Dror (1995) Reduction of Visual Complexity in Dynamic Graphs. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 218-225 (Official URL:

Full text not available from this repository.


Graphs are used extensively in software visualization to represent both static aspects of software structure and dynamic aspects of execution-time behavior. However, for realistic subject software systems, there are far too many nodes and edges in the displayed graphs to be comprehensible to an end user. Further, for presentation of dynamics, continual change and redisplay of such large graphs is too demanding for conventional workstation computational resources. This paper poses the problem of "reduction" or "abstraction" in dynamically changing graphs, and proposes a combination of techniques that can be used to reduce the visual complexity of a graph, without obscuring the significant information that it was meant to convey. The abstract graph can be comprehended more readily and it changes far less frequently than the full graph. As well, when the abstract graph does change, it requires far less computation for layout and redisplay. These abstraction techniques are illustrated by way of examples showing their use in systems for visualization of objekt-oriented and multi-layer software systems.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_373
Classifications:S Software and Systems > S.120 Visualization
D Aesthetics > D.001 General
ID Code:165

Repository Staff Only: item control page


F.J. Brandenburg "Layout Graph Grammars: The Placement Approach", Proc. 4th International Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science 532, Springer-Verlag, 1991, pp. 144-156.

M.J. Carpano "Automatic Display of Hierarchized Graphs for Computer Aided Decision Analysis", IEEE Trans. Systems, Man, and Cybernetics, SMC-10(11), 1980, pp. 705-715.

M.P. Consens, A.O. Mendelzon, and A.G. Ryman "Visualizing and Querying Software Structures" Proc. 14th Intl. Conf. on Software Engineering, 1992, pp. 138-156.

W. De Pauw, R. Helm, D. Kimelman, and J. Vlissides "Visualizing the Behavior of Object-Oriented Systems", Proc. OOPSLA '93 The Eighth Annual ACM Conference on Object-Oriented Programming Systems, Languages and Applications, SIGPLAN Notices 28(10), October 1993, pp. 326-337.

G. Di Battista and R. Tamassia "Incremental Planarity Testing", Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 436-441.

K.M. Fairchild, S.E. Poltrock, and G.W. Furnas "SemNet: Three-Dimensional Graphic Representations of Large Knowledge Bases", in Cognitive Science and its Applications for Human-Computer Interaction, R. Guindon Ed., Lawrence Erlbaum Associates Publishers, 1988, pp. 201-233.

D. Kimelman, B. Rosenburg, and T. Roth "Strata-Various :-) Multi-Layer Visualization of Dynamics in Software System Behavior", Proc. IEEE Visualization '94, October 1994, pp. 172-178.

D. Kimelman and G. Sang'udi "Program Visualization by Integration of Advanced Compiler Technology with Configurable Views", Proc. CNRS-NSF Collaboration Wokshop on Environments and Tools for Parallel Scientific Computing, Saint Hilaire du Touvet, France, J.J. Dongarra and B. Tourancheau, editors, Elsevier Science Publishers, September 1992, pp. 73-84.

E. Kraemer and J. Stasko "The Visualization of Parallel Systems: An Overview", Journal of Parallel and Distributed Computing 18(2), 1993, pp. 105-117.

Y. Hara, A. Keller, P. Rathmann, G. and Wiederhold "Implementing Hybertext Database Relationships Through Aggregations and Exceptions", Stanford Technical Report STAN-CS-91-1381, September 1991.

M.P. Consens, F.C. Eigler, M.Z. Hasan, A.O. Mendelzon, E.G. Noik, A.G. Ryman, and D. Vista "Architecture and Applications of the Hy+ Visualization System", IBM Systems Journal 33(3), 1994, pp. 458-476.

K. Miriyala, S.W. Hornick, and R. Tamassia "An Incremental Approach to Aesthetic Graph Layout", Proc. International Workshop on Computer-Aided Software Engineering (CASE'93), 1993.

M. Nagl "A Tutorial and Bibliographical Survey on Graph Grammars", Proc. of International Workshop on Graph Grammars and Their Applications to Computer Science and Biology, Lecture Notes in Computer Science, 1978.

F.J. Newbery "Edge Concentration: A Method for Clustering Directed Graphs", Proc. 2nd International Workshop on Software Configuration Management, 1989, pp. 76-85.

E.G. Noik "A Space of Presentation Emphasis Techniques for Visualizing Graphs", Proc. Graphics Interface '94, May 1994, pp. 225-234.

S.C. North "Drawing Ranked Digraphs with Recursive Clusters", Private Communication, Draft from November 1993.

B.A. Price, R.M. Baecker, and I.S. Small "A Principled Taxonomy of Software Visualization", Journal of Visual Languages and Computing 4(3), 1993, pp. 211-266.

S.P. Reiss "A Framework for Abstract 3D Visualization", Proc. IEEE Symposium on Visual Languages, August 1993, pp. 108-115.

A. Rudich, D. Zernik, and G. Zodik "Visage - Visualization of Attribute Graphs: A Foundation for a Parallel Programming Environment", Proc. CNRS-NSF Collaboration Workshop on Environments and Tools for Parallel Scientific Computing, Saint Hilaire du Touvet, France, J.J. Dongarra and B. Tourancheau, editors, Elsevier Science Publishers, September 1992, pp. 171-192.

V. Waddle and A. Malhotra "NARC/X Nodes and ARCs Graph Widget API Definition", IBM Research Center Technical Report, 1993.