Jonathan D. Cohen
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.
- BOBROW, L.S. 1981. Elementary Linear Circuit Analysis. Holt, Rinehart, and Winston, New York.Google Scholar
- 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.Google Scholar
- COHEN, J. D. 1995. Highlights: Language- and domain-independent automatic indexing terms for abstracting. J. Am. Soc. Inf. Sci. 46, 3, 162-174. Corrections appear in Vol. 47, Issue 3, page 260. Google Scholar
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. McGraw Hill, New York. Google Scholar
- 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.Google Scholar
- DAVIES, P. M. AND COXON, A. P. M., Eds. 1982. Key Texts in Multidimensional Scaling. Heinemann Educational Books, Exeter, N.H.Google Scholar
- DAMASHEK, M. 1995. Gauging similarity with n-grams: Language-independent categorization of text. Science 267 (Feb. 10), 843-848.Google Scholar
- 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.Google Scholar
- EVERITT, B. S. 1978. Graphical Techniques for Multivariate Data. North-Holland, New York, Ch. 2.Google Scholar
- FISK, C. J., CASKEY, D. L., AND WEST, L.E. 1967. ACCEL: Automated circuit card etching layout. Proc. IEEE 55, 11 (Nov.), 1971-1982.Google Scholar
- FRUCHTERMAN, T. M. J. AND REINGOLD, E.M. 1991. Graph drawing by force-directed placement. Softw. Pract. Exper. 21, 11 (Nov.), 1129-1164. Google Scholar
- KAMADA, T. 1989. Visualizing Abstract Objects and Relations--A Constraint-Based Approach. World Scientific, Singapore. Google Scholar
- KAMADA, T. ANn KAWAI, S. 1989. An algorithm for drawing general unidirected graphs. Inf. Process. Lett. 31, I (Apr. 12), 7-15. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- MANBER, U. 1989. Introduction to Algorithms. Addison-Wesley, Reading, Mass., Sec. 7.7. Google Scholar
- PISSANETZKY, S. 1984. Sparse Matrix Technology. Academic Press, Orlando, Fla., Ch. 4.Google Scholar
- PRESS, W. H., FLANNERY, B. P., TEUKOLS~, S. A., ANn VETTERLING, W.T. 1986. Numerical Recipes. Cambridge University Press, New York.Google Scholar
- 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.Google Scholar
- SAMMON, J. W. 1969. A nonlinear mapping for data structure analysis. IEEE Trans. Comput. C-18, 5 (May), 401-409.Google Scholar
- SHEPARD, R. N. 1962a. The analysis of proximities: Multidimensional scaling with an unknown distance function. I. Psychometrika 27, 2 (June), 125-140.Google Scholar
- SHEPARD, R. N. 1962b. The analysis of proximities: Multidimensional scaling with an unknown distance function. II. Psychometrika 27, 3 (Sept.), 219-246.Google Scholar
- TAMASSIA, R. AND EADES, P. 1989. Algorithms for drawing graphs: An annotated bibliography. Tech. Rep. CS-89-09, Brown Univ., Providence R.I. Feb. Google Scholar
- TORGERSON, W. S. 1952. Multidimensional scaling: I. Theory and method. Psychometrika 417, 4 (Dec.), 401-419.Google Scholar
Index Terms
- Drawing graphs to convey proximity: an incremental arrangement method
Recommendations
(d+1,2) -Track Layout of Bipartite Graph Subdivisions
A ( k ,2- track layout of a graph G consists of a 2- track assignment of G and an edge k -coloring of G with no monochromatic X-crossing . This paper studies the problem of ( k ,2)-track layout of bipartite graph subdivisions. Recently V.Dujmović and ...
Queue Layout of Bipartite Graph Subdivisions
For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmović and D. R. Wood showed that for every ...
Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs
AbstractSymmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, ...
Reviews
Claudio Delrieux
Graphs are becoming popular as a means of visualizing order, accessibility, or distance information. This paper is concerned with efficient methods of conveying vertex proximity, that is, of arranging the vertices so their pairwise screen distances match their target distances. Cohen discusses an adequate measure of the quality of a representation and then presents the method. To evaluate his and other methods, the author defines a family S k of stress functions of a given representation as an accumulation of the difference between vertex spatial configuration and the target distances. S 0 stress measures absolute errors in long and short distances, S 2 penalizes errors in proportion to the target distance, and S 1 is a “semiproportional” measure. These functions are shown to be similar to others presented elsewhere. Now the problem can be restated as a numerical problem consisting of the minimization of S k . This approach has been tried elsewhere and, like many other combinatorial problems, shows little stability or convergence to local minima. (Simulated annealing might be useful here.) The author then proposes an incremental approach to arranging vertices. Given a small portion that can be considered a good starting point, the author develops an algorithm based on the heuristic that chooses close vertices to remain together. He shows that this algorithm is fast and copes with clustering adequately, at least for the examples provided. Minimizing absolute stress converges quickly, but may fail to reach the global minimum. Proportional stress, in contrast, is robust but converges slowly. Thus, semiproportional stress is a good compromise solution.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments