Drawing graphs to convey proximity
ACM Transactions on Computer-Human InteractionPublished 1 September 1997
Jonathan D. Cohen
Citations85
SJR quartileQ1
SJR score1.17
SNIP2.00
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This article deals with rendering graphs to show proximity between vertices by making their configuration (screen) distances reflect their distances in the graph using an arrangement method that achieves good drawings at speeds suitable for user interaction on a desktop computer.
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.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Computers in PhysicsSavitzky-Golay Smoothing Filters
11,624 Citations1990William H. Press, Saul A. Teukolsky
PsychometrikaMultidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis
7,398 Citations1964Joseph B. Kruskal
The fundamental hypothesis is that dissimilarities and distances are monotonically related, and a quantitative, intuitively satisfying measure of goodness of fit is defined to this hypothesis.
Software Practice and ExperienceGraph drawing by force‐directed placement
6,359 Citations1991Thomas M. J. Fruchterman, Edward M. Reingold
A modification of the spring‐embedder model of Eades for drawing undirected graphs with straight edges is presented, developed in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.
PsychometrikaNonmetric Multidimensional Scaling: A Numerical Method
4,882 Citations1964Joseph B. Kruskal
The numerical methods required in the approach to multi-dimensional scaling are described and the rationale of this approach has appeared previously.
IEEE Transactions on ComputersA Nonlinear Mapping for Data Structure Analysis
3,381 Citations1969John W. Sammon
An algorithm for the analysis of multivariate data is presented along with some experimental results that is based upon a point mapping of N L-dimensional vectors from the L-space to a lower-dimensional space such that the inherent data "structure" is approximately preserved.
Information Processing LettersAn algorithm for drawing general undirected graphs
2,771 Citations1989Tomihisa Kamada, Satoru Kawai
PsychometrikaThe Analysis of Proximities: Multidimensional Scaling with an Unknown Distance Function. I.
2,553 Citations1962Roger N. Shepard
The program is proposed as a tool for reductively analyzing several types of psychological data, particularly measures of interstimulus similarity or confusability, by making explicit the multidimensional structure underlying such data.
Computational GeometryAlgorithms for drawing graphs: an annotated bibliography
860 Citations1994Giuseppe Di Battista, Peter Eades +2 more
A bibliographic survey on algorithms whose goal is to produce aesthetically pleasing drawings of graphs is presented, a first attempt to encompass both theoretical and application-oriented papers from disparate areas.
ScienceGauging Similarity with <i>n</i> -Grams: Language-Independent Categorization of Text
535 Citations1995Marc Damashek
A language-independent means of gauging topical similarity in unrestricted text by combining information derived from n-grams with a simple vector-space technique that makes sorting, categorization, and retrieval feasible in a large multilingual collection of documents.
ACM Transactions on GraphicsDrawing graphs nicely using simulated annealing
489 Citations1996Ron Davidson, David Harel
The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely,” and the algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result.
Introduction to Algorithms: A Creative Approach
442 Citations1989Udi Manber
IEEE Transactions on Circuits and SystemsA forced directed component placement procedure for printed circuit boards
258 Citations1979N. Quinn, M.A. Breuer
A new mathematical formulation of the concept of force directed placement is presented, and an efficient computational procedure for solving the resulting system of equations is described.
Journal of the American Society for Information ScienceHighlights: Language- and domain-independent automatic indexing terms for abstracting
136 Citations1995Jonathan Cohen
A method of drawing index terms from text using n‐gram counts, achieving a function similar to, but more general than, a stemmer.
IEEE Transactions on Systems Man and CyberneticsA Heuristic Relaxation Method for Nonlinear Mapping in Cluster Analysis
73 Citations1973C. L. Chang, R. C. T. Lee
A relaxation method mapping high-dimensional sample points to low- dimensional sample points is discussed, which tries to preserve the local interdistance of sample points.
Proceedings of the IEEEACCEL: Automated circuit card etching layout
56 Citations1967C.J. Fisk, D.L. Caskey +1 more
Printed circuit board design time can be greatly reduced by the use of a computer program called ACCEL developed jointly by Sandia Corporation and the Thomas Bede Foundation under contract to Sandia.
CERN Document Server (European Organization for Nuclear Research)Elementary Linear Circuit Analysis
37 Citations1981L.S. Bobrow
This chapter discusses circuit analysis techniques used in computer-Aided Circuit Analysis, as well as basic Elements and Laws, and the Laplace Transforms, which transformed the circuits into two-Port networks.
Visualizing abstract objects and relations : a constraint-based approach
11 Citations1989Tomihisa Kamada
Visualizing abstract objects and relations: a constraint-based approach using LaSalle’s inequality principle to describe the relationships between objects and relationships in an Abelian model.
Elsevier eBooksFundamentals
1 Citations1984Sergio Pissanetzky
This chapter discusses structures and internal representations used for storing lists of numbers, graphs, and various types of sparse matrices and sparse block-partitioned matrices, and the computational algebra of sparse vectors.