A HEURISTIC METHOD FOR THE AUTOMATIC DRAWING OF SYSTEM MODELING GRAPHS
Alain Y. Martel · IIE Transactions · 1993
Graphical modeling formalisms are used for systems analysis and design in several knowledge fields. In the past the graphs associated with a given formalism were produced by hand with the help of templates. Today, however, several computer-aided system modeling tools are available on the market and, in order to be useful, they must be able to quickly display large graphs automatically. Unfortunately, the problem of drawing an arbitrary graph on the plane is NP-hard for most practical drawing criteria. The objective of this paper is to develop heuristic procedures to automatically and timely display arbitrary forests and undirected graphs in an interactive, mouse-driven graphic environment on a micro-computer. A fast geometric algorithm to display a tree with vertices of varying and non-negligible dimensions is presented and a general graph drawing heuristic is derived. The latter is based on the generation of a spanning tree with special properties which can be used to compute the rectangular coordinates of the graph vertices. We conclude with an example and with some comments on the performance of our algorithms.