Unified modelling language (UML) diagrams have become increasingly important in engineering and re-engineering processes for software systems. Of particular interest are UML class diagrams whose purpose is to display generalizations, associations, aggregations, and compositions in one picture. The combination of directed and undirected relations poses a special challenge to a graph layout tool. Current approaches for the automatic layout of class diagrams are based on the layered graph drawing paradigm. These algorithms produce good results for class diagrams with large and deep structural information, that is, diagrams with a large and deep inheritance hierarchy. However, they do not perform satisfactorily in absence of this information. We suggest to use the topology-shape—metrics paradigm for automatic layout of class diagrams, which has been used very successfully for drawing undirected graphs in orthogonal style. Moreover, we introduce the algorithms UML-Kandinsky and GoVisual fitting into this paradigm. Both algorithms work for class diagrams with rich structural information as well as for class diagrams with few or no structural information. Therefore, they improve the existing algorithms significantly.
BoochGRumbaughJJacobsonI.Unified Modeling Language User Guide. Addison-Wesley, Longman: Reading MA, 1999.
2.
PurchaseHAllderJ-ACarringtonD.User preference of graph layout aesthetics: A UML study. In: MarksJ (Ed), Graph Drawing (Proc. GD 2000). Lecture Notes in Computer Science, Vol. 1984Springer-Verlag: Berlin, 2001; 5–18.
3.
PurchaseHC. Which aesthetic has the greatest effect on human understanding?. In: Proceedings of the 5th International Symposium on Graph Drawing (GD1997). Vol. 1353, Springer: Berlin, 1997; 248–261.
4.
PurchaseHCCohenRFJamesM.An experimental study of the basis for graph drawing algorithms. ACM Journal of Experimental Algorithmics, 1997; 2: 4.
5.
EichelbergerH.Aesthetics of class diagrams. In: Proceedings of the First IEEE International Workshop on Visualizing Software for Understanding and Analysis, Vissoft, 2002; 2002: 23–31.
TogetherSoft Corporation Together Control Center. 2002.
8.
SeemannJ.Extending the sugiyama algorithm for drawing UML class diagrams. In: Di BattistaG (Ed), Graph Drawing (Proc. GD 1997). Vol. 1353, Springer: Berlin, 1997; 415–424.
9.
SugiyamaKTagawaSTodaM.Methods for visual understanding of hierarchical systems. IEEE Transations on System, Man and Cybernetics, 1981; SMC-11: 109–125.
Di BattistaGEadesPTamassiaRTollisIG. Graph Drawing. Prentice-Hall: Englewood Cliffs, NJ, 1998.
17.
TamassiaRBattistaGDBatiniC.Automatic graph drawing and readability of diagrams. IEEE Transations on System, Man and Cybernetics, 1998; SMC-18: 61–79.
18.
LempelAEvenSCederbaumI.An algorithm for planarity testing of graphs. In: Theory of Graphs: International Symposium (Rome). Gordon and Breach: New York, 1967; 215–232.
19.
BoothKLuekerG.Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 1976; 13: 335–379.
ChibaNNishizekiTAbeSOzawaT.A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 1985; 30: 54–76.
22.
MehlhornKMutzelP.On the embedding phase of the Hopcoft and Tarjan planarity testing algorithm. Algorithmica, 1996; 16: 233–242.
23.
LiuPCGeldmacherRC. On the deletion of nonplanar edges of a graph. In: Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1977; 727–738.
24.
JüngerMMutzelP.Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, Special Issue on Graph Drawing, 1996; 16: 33–59.
25.
CaiJHanXTarjanRE. An O(m log n)-time algorithm for the maximal planar subgraph problem. SIAM Journal on Computing, 1993; 22: 1142–1162.
26.
JüngerMLeipertSMutzelP.A note on computing a maximal planar subgraph using PQ-trees. IEEE Transactions on Computer-Aided Design, 1998; 17: 609–612.
27.
GutwengerCMutzelP.An experimental study of crossing minimization heuristics. In: LiottaG (Ed), Graph Drawing (Proc. GD 1903). Lecture Notes in Computer Science. Vol. 2912, Springer-Verlag: Berlin, 2004; 2912: 13–24.
28.
TamassiaR.On embedding a graph in the grid with the minimum number of bends. SIAM Journal of Computing, 1987; 16: 421–444.
29.
GargATamassiaR.On the complexity of upward and rectilinear planarity testing. In: Proceedings of the 2nd International Symposium on Graph Drawing (GD1994). Lecture Notes in Computer Science, Vol. 894, Springer: Berlin, 1995; 286–297.
30.
FössmeierUKaufmannM.Drawing high degree graphs with low bend numbers. In: BrandenburgFJ (Ed), Proceedings of the 3rd International Symposium on Graph Drawing (GD1995). Vol. 1027, Springer: Berlin, 1996; 254–266.
31.
BertolazziPBattistaGDDidimoW.Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 2000; 49: 826–840.
32.
MutzelPWeiskircherR.Computing optimal embeddings for planar graphs. In: DuD-ZEadesPEstivill-CastroVLinXSharmaA (Eds.). Computing and Combinatorics Proceedings of the Sixth Annual International Conference (COCOON 192000). Lecture Notes in Computer Science, Vol. 1858, Springer-Verlag: Berlin, 2000; 95–104.
33.
PatrignaniM.On the complexity of orthogonal compaction. Technical. Report. RT-DIA-39–99, Dipartimento di Informatica e Automazione, Università degli Studi di Roma Tre, January, 1999.
Di BattistaGDidimoWPatrignaniMPizzoniaM.Orthogonal and quasi-upward drawings with vertices of prescribed size. In: Proceedings of the 7th International Symposium on Graph Drawing (GD1999). Lecture Notes in Computer Science, KratochvilJ (Ed), Vol. 1731, Springer: Berlin, 1999; 297–310.
36.
EiglspergerMKaufmannM.Fast compaction for orthogonal drawings with vertices of prescribed size. In: Proceedings of the 9th International Symposium on Graph Drawing (GD192001). Vol. 2265, Springer: Berlin, 2001; 124–138.
37.
BertolazziPDi BattistaGManninoCTamassiaR.Optimal upward planarity testing of single-source digraphs. SIAM Journal on Computing, 1998; 27: 132–169.
EiglspergerMKaufmannMEppingerF.An approach for mixed upward planarization. Journal of Graph Algorithms and Applications, 2003; 7: 203–220.
40.
EiglspergerMFoessmeierUKaufmannM.Orthogonal graph drawing with constraints. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, 2000; 3–11.
41.
WagnerFWolffA.A combinatorial framework for map labeling. In: Proceedings of the 6th International Symposium on Graph Drawing (GD1998). Lecture Notes in Computer Science, Vol. 1547, Springer: Berlin, 1998; 316–331.
42.
KlauGWMutzelP.Optimal labelling of point features in the slider model. In: DuD-ZEadesPEstivill-CastroVLinXSharmaA (Eds.). Computing and Combinatorics, Proceedings of the Sixth Annual International. Conference. (COCOON 192000). Lecture Notes in Computer Science, Vol. 1858, Springer-Verlag: Berlin, 2000; 340–350.
43.
KlauGWMutzelP.Combining graph labeling and compaction. In: KratochvilJ (Ed), Proceedings of the 7th International Symposium on Graph Drawing (GD1999). Lecture Notes in Computer Science, Vol. 1731, Springer: Berlin, 1999; 27–37.
44.
BinucciCDidimoWLiottaGNonatoM.Labeling heuristics for orthogonal drawings. In: Proceedings of the 9th International Symposium on Graph Drawing (GD192001), Lecture Notes in Computer Science. Vol. 2275, Springer: Berlin, 2001; 139–153.
45.
BinucciCDidimoWLiottaGNonatoM.Computing labeled orthogonal drawings. In: Proceedings of the 10th International Symposium on Graph Drawing (GD192002). Lecture Notes in Computer Science, Vol. 2528, Springer: Berlin, 2002; 66–73.
46.
FengQ-WCohenRFEadesP.Planarity for clustered graphs. In: SpirakisP (Ed), Algorithms - ESA 1995. Lecture Notes in Computer Science, Vol. 979, Springer Verlag: Berlin, 1995; 213–226.
47.
GutwengerCJüngerMLeipertSMutzelPPercanMWeiskircherR.Advances in c-planarity testing of clustered graphs. In: GoodrichMKobourovS (Eds.). Graph Drawing (Proc. 2002). Lecture Notes in Computer Science, Vol. 2528, Springer-Verlag: Berlin, 2002; 220–235.
Lütke-HüttemannD.Knickminimales Zeichnen 4-planarer Clustergraphen. Master's thesis, Universität des Saarlands. 1977.
50.
EiglspergerMKaufmannMSiebenhallerM.A topology-shapemetrics approach for the automatic layout of uml class diagrams. In: Proceedings of The ACM 2003 Symposium on Software Visualization. ACM:New York, 2003; 189–198.
LengauerT.Combinatorial Algorithms for Integrated Circuit Layout. Applicable Theory in Computer Science. Wiley-Teubner: New York, 1990.
53.
FreiwaldsKDogrusozUKikustsP.Disconnected graph layout and the polyomino packing approach. In: Proceedings of the 9th International Symposium on Graph Drawing (GD192001). Lecture Notes in Computer science, Vol. 2265, Springer: Berlin, 2001; 378–391.
54.
BrandesUEiglspergerMKaufmannMWagnerD.Sketch-driven orthogonal graph drawing. In: Proceedings of the 10th International Symposium on Graph Drawing (GD192002). Vol. 2528, Springer: Berlin, 2002; 1–12.
55.
WieseREiglspergerMKaufmannM.yfiles: visualization and automatic layout of graphs. In: Proceedings of the 9th International Symposium on Graph Drawing (GD1901). Lecture Notes in Computer Science, Springer: Berlin, 2001; 453–454.
56.
EadesPKellyD.Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria, 1986; 21: 89–98.
57.
GansnerERKoutsofiosENorthSCVoKP. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 1993; 19: 214–230.
58.
JüngerMMutzelP.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/), 1996; 1: 1–25.
59.
KlauGWMutzelP.Quasi-orthogonal drawing of planar graphs. Technical. Report. MPI-I-98–1–013, Max-Planck-Institut für Informatik, Saarbrücken. 1998.
GutwengerCJungerMKleinKKupkaJLeiperhSMutzelP.A new approach for visualizing uml class diagrams. In: Proceedings of the ACM 2003 Symposium on Software Visualization. ACM: New York, 2003; 179–188.
