Drawing graphs to convey proximity: an incremental arrangement method

ABSTRACT

Graph drawings are increasingly finding their way into user interfaces to convey a variety of relationships. This article deals with rendering graphs to show proximity between vertices by making their configuration (screen) distances reflect their distances in the graph. An arrangement method is described that achieves good drawings at speeds suitable for user interaction on a desktop computer. The method is “incremental” in that it first arranges a small portion of the graph, then arranges successively larger fractions of the graph until a suitable arrangement for the entirety is achieved. The incremental approach not only offers speed improvements, but avoids many of the suboptimal solutions reached with other iterative approaches. Algorithms are described in pseudocode, and results are presented.

REFERENCES

• 1: BOBROW, L.S. 1981. Elementary Linear Circuit Analysis. Holt, Rinehart, and Winston, New York.
• 2: CHANG, C. L. ANn LEE, R. C.T. 1973. A heuristic relation method for nonlinear mapping in the cluster analysis. IEEE Trans. Syst. Man Cybernet. SMC-3, 2 (Mar.), 197-200.
• 3: Jonathan D. Cohen, Highlights: language- and domain-independent automatic indexing terms for abstracting, Journal of the American Society for Information Science, v.46 n.3, p.162-174, April 1995 [doi>10.1002/(SICI)1097-4571(199504)46:3<162::AID-ASI2>3.0.CO;2-6]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: DAVIDSON, R. ANn HAREL, D. 1989. Drawing graphs nicely using simulated annealing. Tech. Rep. CS89-13, Dept. of Applied Mathematics and Computer Science, The Weizmann Inst., Rehovot, Israel. July.
• 6: DAVIES, P. M. AND COXON, A. P. M., Eds. 1982. Key Texts in Multidimensional Scaling. Heinemann Educational Books, Exeter, N.H.
• 7: DAMASHEK, M. 1995. Gauging similarity with n-grams: Language-independent categorization of text. Science 267 (Feb. 10), 843-848.
• 8: EADES, P. 1984. A heuristic for graph drawing. Congressus Numerantium: Proceedings of the 13th Manitoba Conference on Numerical Mathematics and Computing (Sept.-Oct.). Vol. 24. Utilitas Mathematica, University of Manitoba, Winnipeg, Canada.
• 9: EVERITT, B. S. 1978. Graphical Techniques for Multivariate Data. North-Holland, New York, Ch. 2.
• 10: FISK, C. J., CASKEY, D. L., AND WEST, L.E. 1967. ACCEL: Automated circuit card etching layout. Proc. IEEE 55, 11 (Nov.), 1971-1982.
• 11: Thomas M. J. Fruchterman , Edward M. Reingold, Graph drawing by force-directed placement, Software—Practice & Experience, v.21 n.11, p.1129-1164, Nov. 1991 [doi>10.1002/spe.4380211102]
• 12: Tomihisa Kamada, Visualizing Abstract Objects and Relations, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 13: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 14: KRUSKAL, J. 1964a. Multidimensional scaling by optimizing goodness-of-fit to a nonmetric hypothesis. Psychometrika 29, 1-27. Reprinted in Key Texts in Multidimensional Scaling, P. M. Davies and A. P. M. Coxon, Eds. Heinemann Educational Books, Exeter, N.H., 1982, pp. 59-83.
• 15: KRUSKAL, J. 1964b. Non-metric multidimensional scaling: A numerical method. Psychometrika 29, 115-129. Reprinted in Key Texts in Multidimensional Scaling, P. M. Davies and A. P. M. Coxon, Eds. Heinemann Educational Books, Exeter, N.H., 1982, pp. 84-97.
• 16: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: PISSANETZKY, S. 1984. Sparse Matrix Technology. Academic Press, Orlando, Fla., Ch. 4.
• 18: PRESS, W. H., FLANNERY, B. P., TEUKOLS~, S. A., ANn VETTERLING, W.T. 1986. Numerical Recipes. Cambridge University Press, New York.
• 19: QUINN, N. R., JR. ANn BREUER, M.A. 1979. A force directed component placement procedure for printed circuit boards. IEEE Trans. Circuits Syst. CAS-26, 6 (June), 377-388.
• 20: SAMMON, J. W. 1969. A nonlinear mapping for data structure analysis. IEEE Trans. Comput. C-18, 5 (May), 401-409.
• 21: SHEPARD, R. N. 1962a. The analysis of proximities: Multidimensional scaling with an unknown distance function. I. Psychometrika 27, 2 (June), 125-140.
• 22: SHEPARD, R. N. 1962b. The analysis of proximities: Multidimensional scaling with an unknown distance function. II. Psychometrika 27, 3 (Sept.), 219-246.
• 23: Peter Eades , Roberto Tamassia, Algorithms for Drawing Graphs: An Annotated Bibliography, Brown University, Providence, RI, 1988
• 24: TORGERSON, W. S. 1952. Multidimensional scaling: I. Theory and method. Psychometrika 417, 4 (Dec.), 401-419.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Screen design (e.g., text, graphics, color)

General Terms:
Algorithms, Human Factors, Performance

Keywords:
MDS, force-directed, graph drawing, graph layout, multidimensional scaling