A new approach for visualizing UML class diagrams

ABSTRACT

UML diagrams have become increasingly important in the engineering and reengineering processes for software systems. Of particular interest are UML class diagrams whose purpose is to display class hierarchies (generalizations), associations, aggregations, and compositions in one picture. The combination of hierarchical and non-hierarchical relations poses a special challenge to a graph layout tool. Existing layout tools treat hierarchical and non-hierarchical relations either alike or as separate tasks in a two-phase process as in, e.g., [Seemann 1997]. We suggest a new approach for visualizing UML class diagrams leading to a balanced mixture of the following aesthetic criteria: Crossing minimization, bend minimization, uniform direction within each class hierarchy, no nesting of one class hierarchy within another, orthogonal layout, merging of multiple inheritance edges, and good edge labelling. We have realized our approach within the graph drawing library GoVisual. Experiments show the superiority to state-of-the-art and industrial standard layouts.

REFERENCES

• 1: BATTISTA, G. D., EADES, P., TAMASSIA, R., AND TOLLIS, I. 1999. Graph Drawing. Prentice Hall.
• 2: Paola Bertolazzi , Giuseppe Di Battista , Carlo Mannino , Roberto Tamassia, Optimal Upward Planarity Testing of Single-Source Digraphs, SIAM Journal on Computing, v.27 n.1, p.132-169, Feb. 1998 [doi>10.1137/S0097539794279626]
• 3: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 4: BOOTH, K., AND LUEKER, G. 1976. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13, 335--379.
• 5: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• 6: DI BATTISTA, G., EADES, P., TAMASSIA, R., AND TOLLIS, I. G. 1998. Graph Drawing. Prentice Hall.
• 7: Giuseppe Di Battista , Walter Didimo , A. Marcandalli, Planarization of Clustered Graphs, Revised Papers from the 9th International Symposium on Graph Drawing, p.60-74, September 23-26, 2001
• 8: EADES, P., AND KELLY, D. 1986. Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria 21, A, 89--98.
• 9: EICHELBERGER, H. 1999. Entwicklung eines Frameworks zum automatischen Zeichnen von Software-Entwurfsdiagrammen. Master's thesis, Universität Wüzburg.
• 10: EICHELBERGER, H. 2002. SugiBib. In Graph Drawing (Proc. GD '01), Springer-Verlag, P. Mutzel, M. Jünger, and S. Leipert, Eds., vol. 2265 of Lecture Notes in Computer Science, 467--468.
• 11: Markus Eiglsperger , Michael Kaufmann, An Approach for Mixed Upward Planarization, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.352-364, August 08-10, 2001
• 12: Qing-Wen Feng , Robert F. Cohen , Peter Eades, Planarity for Clustered Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.213-226, September 25-27, 1995
• 13: E. R. Gansner , E. Koutsofios , S. C. North , K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, v.19 n.3, p.214-230, March 1993 [doi>10.1109/32.221135]
• 14: Ashim Garg , Roberto Tamassia, On the Compuational Complexity of Upward and Rectilinear Planarity Testing, Proceedings of the DIMACS International Workshop on Graph Drawing, p.286-297, October 10-12, 1994
• 15: Carsten Gutwenger , Petra Mutzel , René Weiskircher, Inserting an edge into a planar graph, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.246-255, January 07-09, 2001, Washington, D.C., United States
• 16: Carsten Gutwenger , Michael Jünger , Sebastian Leipert , Petra Mutzel , Merijam Percan , René Weiskircher, Advances in C-Planarity Testing of Clustered Graphs, Revised Papers from the 10th International Symposium on Graph Drawing, p.220-235, August 26-28, 2002
• 17: HARARY, F. 1972. Graph Theory. Addison Wesley.
• 18: JÜNGER, M., AND MUTZEL, P. 1996. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications (JGAA) (http://www.cs.brown.edu/publications/jgaa/) 1, 1, 1--25.
• 19: JÜNGER, M., LEIPERT, S., AND MUTZEL, P. 1998. A note on computing a maximal planar subgraph using PQ-trees. IEEE Transactions on Computer-Aided Design 17, 7, 609--612.
• 20: KLAU, G. W., AND MUTZEL, P. 1998. Quasi-orthogonal drawing of planar graphs. Tech. Rep. MPI-I-98-1-013, Max--Planck--Institut für Informatik, Saarbrücken.
• 21: Gunnar W. Klau , Karsten Klein , Petra Mutzel, An Experimental Comparison of Orthogonal Compaction Algorithms (Extended Abstract), Proceedings of the 8th International Symposium on Graph Drawing, p.37-51, September 20-23, 2000
• 22: LEMPEL, A., EVEN, S., AND CEDERBAUM, I. 1967. An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium: Rome, July 1966, Gordon and Breach, New York, 215--232.
• 23: Helen C. Purchase , Jo-Anne Allder , David A. Carrington, User Preference of Graph Layout Aesthetics: A UML Study, Proceedings of the 8th International Symposium on Graph Drawing, p.5-18, September 20-23, 2000
• 24: RATIONAL SOFTWARE CORPORATION, 2002. Rational Rose, Rational XDE.
• 25: Jochen Seemann, Extending the Sugiyama Algorithm for Drawing UML Class Diagrams: Towards Automatic Layout of Object-Oriented Software Diagrams, Proceedings of the 5th International Symposium on Graph Drawing, p.415-424, September 18-20, 1997
• 26: SUGIYAMA, K., TAGAWA, S., AND TODA, M. 1981. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern. SMC-11, 2, 109--125.
• 27: Roberto Tamassia , Giuseppe Di Battista , Carlo Batini, Automatic graph drawing and readability of diagrams, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.61-79, January/February 1988 [doi>10.1109/21.87055]
• 28: Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
• 29: TOGETHERSOFT CORPORATION, 2002. Together ControlCenter.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Graphical environments

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Keywords:
UML Class Diagrams, graph drawing, graph layout, software visualization