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
Simulated annealingComputer scienceUndirected graphGraph drawingAlgorithmSimple (philosophy)Line graphMathematical optimizationTheoretical computer scienceGraphMathematics
Affiliated Institutions
Related Publications
Graph drawing by force‐directed placement
Abstract We present a modification of the spring‐embedder model of Eades [Congressus Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heu...
Dynamic Multilevel Graph Visualization
We adapt multilevel, force-directed graph layout techniques to visualizing dynamic graphs in which vertices and edges are added and removed in an online fashion (i.e., unpredict...
An Efficient Heuristic Procedure for Partitioning Graphs
We consider the problem of partitioning the nodes of a graph with costs on its edges into subsets of given sizes so as to minimize the sum of the costs on all edges cut. This pr...
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
In this paper, we discuss consensus problems for networks of dynamic agents with fixed and switching topologies. We analyze three cases: 1) directed networks with fixed topology...
Publication Info
- Year
- 1996
- Type
- article
- Volume
- 15
- Issue
- 4
- Pages
- 301-331
- Citations
- 481
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
481
OpenAlex
Cite This
Ron Davidson,
David Harel
(1996).
Drawing graphs nicely using simulated annealing.
ACM Transactions on Graphics
, 15
(4)
, 301-331.
https://doi.org/10.1145/234535.234538
Identifiers
- DOI
- 10.1145/234535.234538