Force-directed algorithms have been developed over the last 50 years and used in many application fields, including information visualisation, biological network visualisation, sensor networks, routing algorithms, scheduling, graph drawing, etc. Our survey provides a comprehensive summary of developments and a full roadmap for state-of-the-art force-directed algorithms in schematic drawings and placement.
We classified the model of force-directed algorithms into classical and hybrid. The classical force-directed algorithms are further classified as follows: (a) accumulated force models, (b) energy function minimisation models, and (c) combinatorial optimisation models. The hybrid force-directed algorithms are classified as follows: (a) parallel and hardware accelerated models, (b) multilevel force-directed models, and (c) multidimensional scaling force-directed algorithms. Five categories of application domains in which force-directed algorithms have been adopted for schematic drawings and placement are also summarised: (a) aesthetic drawings for general networks, (b) component placement and scheduling in high-level synthesis of very-large scale integration (VLSI) circuits design, (c) information visualisation, (d) biological network visualisation, and (e) node placement and localisation for sensor networks.
The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/Force-directed-algorithms-for-schematic-drawings-and-placement：a-Survey.pdf. Se-Hang Cheong, Yain-Whar Si. "Force-directed algorithms for schematic drawings and placement: A survey", Information Visualization, Accepted and to appear, Sage, 2019.
Force-directed algorithms are widely used for visualizing graphs. However, these algorithms are computationally expensive in producing good quality layouts for complex graphs. The layout quality is largely influenced by execution time and methods’ input parameters especially for large complex graphs. The snapshots of visualization generated from these algorithms are useful in presenting the current view or a past state of an information on timeslices. Therefore, researchers often need to make a trade-off between the quality of visualization and the selection of appropriate force-directed algorithms.
In this paper, we evaluate the quality of snapshots generated from 7 force-directed algorithms in terms of number of edge crossing and the standard deviations of edge length. Our experimental results showed that KK, FA2 and DH algorithms cannot produce satisfactory visualizations for large graphs within the time limit. KK-MS-DS algorithm can process large and planar graphs but it does not perform well for graphs with low average degrees. KK-MS algorithm produces better visualizations for sparse and non-clustered graphs than KK-MS-DS algorithm.
The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/Snapshot-Visualization-of-Complex-Graphs-with-Force-directed-Algorithms.pdf.
Se-Hang Cheong, Yain-Whar Si. "Snapshot Visualization of Complex Graphs with Force-directed Algorithms", Proceedings of the IEEE International Conference on Big Knowledge (ICBK), pp. 139-145, IEEE Press, 2018.
A graph layout problem, or visualization problem, refers to a set of nodes and a set of relationships (edges) built on top of this set of nodes, calculating the position of the nodes and drawing each edge as a line or curve.
One of the most important research directions in the visualization technology of graphs is the study of graph layout algorithms. The core content of the graph layout algorithm research is to study how to display the graph structure in a better way. E.g. force-directed algorithms.
The comprehensive workflow for classical force-directed algorithms are summarized below:
- Davidson and Harel Algorithm
- LinLog Algorithm
- Kamada-Kawai Algorithm
- Fruchterman Reingold Algorithm
- ForceAtlas2 Algorithm
1. Davidson and Harel Algorithm
2. LinLog Algorithm
3. Kamada-Kawai Algorithm
4. Fruchterman Reingold Algorithm
5. ForceAtlas2 Algorithm
A layered approach to analysis and visualization of associations from events can provide different levels of abstraction for aggregating and analyzing events from heterogeneous data sources by using lists and customizable functions.
Si, Yain-Whar, Se-Hang Cheong, Simon Fong, Robert P. Biuk-Aghai, and Tat-Man Cheong. "A layered approach to link analysis and visualization of event data." In Digital Information Management (ICDIM), 2012 Seventh International Conference on, pp. 181-185. IEEE, 2012. The author’s version of a work that was accepted for publication can be downloaded from http://eric.lostcity-studio.com/wp-content/uploads/2019/08/ICDIM2012-AuthorCopy.pdf.