An algorithm for blob hierarchy layout

ABSTRACT

We present an algorithm for the aesthetic drawing of basic hierarchical blob structures, of the kind found in higraphs and statecharts and in other diagrams in which hierarchy is depicted as topological inclusion. Our work could also be useful in window system dynamics, and possibly also in things like newspaper layout, etc. Several criteria for aesthetics are formulated, and we discuss their motivation, our methods of implementation and the algorithm's performance.

REFERENCES

• 1: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 2: Ron Davidson , David Harel, Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics (TOG), v.15 n.4, p.301-331, Oct. 1996 [doi>10.1145/234535.234538]
• 3: Eades, P., Feng, Q. W., Lin, X., and Nagamochi, H., Straight Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs, Technical Report 98-03, Department of Computer Science, University of Newcastle, 1998.
• 4: Eades, P., and Feng, Q. W., Multilevel Visualization of Clustered Graphs, Technical Report 96-09, Department of Computer Science, University of Newcastle, 1996.
• 5: Eades, P., Lin, T., and Lin, X., Two Tree Drawing Conventions, Int. J. Comput. Geom. Appl. 3 (1993), 133 - 153.
• 6: Eades, P., Lin, T., and Lin, X., Minimum Size h-v Drawings, In Proc. of Conf. on Advanced Visual Interfaces (AVI '92), World Series in Computer Science 36:2, 1993, pp. 133- 153.
• 7: Eades, P., Lin, T., and Tamassia, R., An Algorithm for Drawing a Hierarchical Graph, Int. J. Comput. Geom. Appl., 6 (1996), 145- 155.
• 8: David Harel, On visual formalisms, Communications of the ACM, v.31 n.5, p.514-530, May 1988 [doi>10.1145/42411.42414]
• 9: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 10: David Harel , Eran Gery, Executable Object Modeling with Statecharts, Computer, v.30 n.7, p.31-42, July 1997 [doi>10.1109/2.596624]
• 11: David Harel , Amir Pnueli , Hagi Lachover , Amnon Naamad , Michal Politi , Rivi Sherman , Aharon Shtull-Trauring , Mark Trakhtenbrot, STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, v.16 n.4, p.403-414, April 1990 [doi>10.1109/32.54292]
• 12: David Harel , Michal Politi, Modeling Reactive Systems with Statecharts: The Statemate Approach, McGraw-Hill, Inc., New York, NY, 1998
• 13: Documents on the Unified Modeling Language (UML), available from the Object Management Group (OMG), http://www.omg.org.
• 14: Eser Kandogan , Ben Shneiderman, Elastic windows: improved spatial layout and rapid multiple window operations, Proceedings of the workshop on Advanced visual interfaces, May 27-29, 1996, Gubbio, Italy [doi>10.1145/948449.948454]
• 15: G. Kant , G. Liotta , R. Tamassia , I. G. Tollis, Area Requirement of Visibility Representations of Trees, Brown University, Providence, RI, 1996
• 16: Panagiotis Takis Metaxas , Grammati E. Pantziou , Antonios Symvonis, Parallel h-v Drawings of Binary Trees, Proceedings of the 5th International Symposium on Algorithms and Computation, p.487-495, August 25-27, 1994
• 17: Maimone, M. W., Tygar, J. D., and Wing, J. M., Formal Semantics for Visual Specification of Security, In Visual Languages and Visual Programming, Plenum Press, New York, 1990, pp. 54- 64.
• 18: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 19: Sigiyama, K., Tagawa, S., and Toda, M., Methods for Visual Understanding of Hierarchical System Structures, IEEE Tran. Syst., Man., Cybern. SMC- 11 (1981), 109 - 125.
• 20: David Turo, Hierarchical visualization with treemaps: making sense of pro basketball data, Conference companion on Human factors in computing systems, p.441-442, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/259963.260441]
• 21: David Turo , Brian Johnson, Improving the visualization of hierarchies with treemaps: design issues and experimentation, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
blob, hierarchy, higraph, layout