Drawing graphs nicely using simulated annealing
ACM Transactions on GraphicsPublished 1 October 1996Open access
Ron Davidson, David Harel
Citations489
SJR quartileQ1
SJR score2.96
SNIP3.06
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
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.
Abstract
The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely.” Our algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result. The algorithm is flexible, in that the relative weights of the criteria can be changed. For graphs of modest size it produces good results, competitive with those produced by other methods, notably, the “spring method” and its variants.
Keywords
Computer Science
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
Applied mathematical sciencesA Practical Guide to Splines
11,999 Citations1978Carl de Boor
This book presents those parts of the theory which are especially useful in calculations and stresses the representation of splines as linear combinations of B-splines as well as specific approximation methods, interpolation, smoothing and least-squares approximation, the solution of an ordinary differential equation by collocation, curve fitting, and surface fitting.
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.
Mathematics and Computers in SimulationSimulated annealing: theory and applications.
3,005 Citations1988
Information Processing LettersAn algorithm for drawing general undirected graphs
2,771 Citations1989Tomihisa Kamada, Satoru Kawai
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
1,468 Citations1989David S. Johnson, C. Aragon +2 more
This paper discusses annealing and its parameterized generic implementation, describes how this generic algorithm was adapted to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm.
Communications of the ACMOn visual formalisms
1,269 Citations1988David Harel
The higraph, a general kind of diagramming object, forms a visual formalism of topological nature that is suited for a wide array of applications to databases, knowledge representation, and the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
IEEE Transactions on Software EngineeringSTATEMATE: a working environment for the development of complex reactive systems
1,117 Citations1990David Harel, H. Lachover +6 more
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.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
844 Citations1991David S. Johnson, C. Aragon +2 more
This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization.
SIAM Journal on Algebraic and Discrete MethodsCrossing Number is NP-Complete
661 Citations1983M. R. Garey, David S. Johnson
This paper shows that there is not likely to be any efficient way to design an optimal embedding of a graph or network in a planar surface, and hence this problem is NP-complete.
IEEE Transactions on Systems Man and CyberneticsAutomatic graph drawing and readability of diagrams
378 Citations1988Roberto Tamassia, Giuseppe Di Battista +1 more
The algorithm presented draws graphs on a grid and is suitable for both undirected graphs and mixed graphs that contain as subgraphs hierarchic structures.
A tutorial survey of theory and applications of simulated annealing
149 Citations1985Bruce Hajek
The basic theory of simulated annealing is reviewed, its recent applications are surveyed, and the theoretical approaches that have been used to study the technique are surveyed.
Software Practice and ExperienceDAG—a program that draws directed graphs
130 Citations1988Emden R. Gansner, Stephen C. North +1 more
DAG is a program that draws directed graphs by reading a list of noeds and edges, computing a layout and then writing a PIC or PostScript description of a picture, which works best on directed acyclic graphs.
Journal of Systems and SoftwareComputer aided layout of entity relationship diagrams
88 Citations1984Carlo Batini, Maurizio Talamo +1 more
An algorithm that allows computer aided layout of entity relationship diagrams on a grid and a standard for the representation of symbols is introduced and aesthetic criteria that should be achieved by a layout algorithm are proposed.
Journal of Graph TheoryHypergraph planarity and the complexity of drawing venn diagrams
76 Citations1987David S. Johnson, H. O. Pollak
This work introduces two new notions of planarity for hypergraphs based on dual generalizations of the standard Venn diagram, and shows that the general problem of determining whether such diagrams exist is NP-complete.
A method for drawing graphs
63 Citations1985R.J. Lipton, Stephen C. North +1 more
The authors are developing programs that draw pictures of graphs in the plane, and there are au infinite number of pictures that represent a given graph.
International Journal of Computer MathematicsHow to draw a hypergraph
57 Citations1990Erkki Mäkinen
This paper shows that in many cases the problem of drawing a hypergraph can be reduced to the problem to drawing normal graphs, i.e. when the hyperedges connecting the vertices are drawn as curves.
IEEE Transactions on Software EngineeringMiro: visual specification of security
52 Citations1990Allan Heydon, Mark Maimone +3 more
Miro is a set of languages and tools that support the visual specification of file system security, and two visual languages are presented: the instance language and the constraint language, which allows specification of security policies.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsThermodynamic Optimization of Block Placement
30 Citations1987Patrick Siarry, L. Bergonzi +1 more
This paper presents the results of a systematic investigation of the thermodynamic ("simulated annealing") method applied to the placement of rectangular blocks on a chip, and a new presentation of the fundamental ideas underlying this technique is proposed.
Journal of Visual Languages & ComputingRandomized Graph Drawing with Heavy-Duty Preprocessing
21 Citations1995David Harel, Meir Sardas
On the Automated Drawing of Graphs
11 Citations1981Margaret Bernard
This paper considers the procedure for the automatic drawing of trees, and graphs displaying symmetry properties, based on a computer system for the adrawing of graphs.
eCommons (Cornell University)An Incremental Drawing Algorithm for Planar Graphs
3 Citations1995David Harel, Meir Sardas
This work presents a new algorithm for drawing planar graphs on the plane that does not require a preliminary triangulation step and is viewed as a generalization of the algorithm of Chrobak and Payne, which in turn is based on an algorithm by de Fraysseix, Pach and Pollack.