Axis-by-Axis Stress Minimization

Koren, Yehuda and Harel, David (2004) Axis-by-Axis Stress Minimization. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 450-459 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_42).

Full text not available from this repository.

Abstract

Graph drawing algorithms based on minimizing the so-called stress energy strive to place nodes in accordance with target distances. They were first introduced to the graph drawing field by Kamada and Kawai [11], and they had previously been used to visualize general kinds of data by multidimensional scaling. In this paper we suggest a novel algorithm for the minimization of the Stress energy. Unlike prior stress-minimization algorithms, our algorithm is suitable for a one-dimensional layout, where one axis of the drawing is already given and an additional axis needs to be computed. This 1-D drawing capability of the algorithm is a consequence of replacing the traditional node-by-node optimization with a more global axis-by-axis optimization. Moreover, our algorithm can be used for multidimensional graph drawing, where it has time and space complexity advantages compared with other stress minimization algorithms.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_42
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.400 Force-directed / Energy-based
ID Code:474

Repository Staff Only: item control page

References

L. Carmel, D. Harel and Y. Koren, "Drawing Directed Graphs Using One-Dimensional Optimization", Proc. Graph Drawing 2002, LNCS 2528, pp. 193-206, Springer-Verlag, 2002.

L. Carmel, D. Harel and Y. Koren, "Combinding Hierarchy and Energy for Drawing Directed Graphs", IEEE Transactions on Visualization and Computer Graphics, IEEE, in press.

J.D. Cohen, "Drawing Graphs to Convey Proximity: an Incremental Arrangement Method", ACM Transactions on Computer-Human Interaction 4 (1997), 197-229.

P. Gajer, M.T. Goodrich and S.G. Kobourov, "A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs", Proc. Graph Drawing 2000, LNCS 1984, pp. 211-221, Springer-Verlag, 2000.

R. Hadany and D. Harel, "A Multi-Scale Method for Drawing Graphs Nicely", Discrete Applied Mathematics 113 (2001), 3-21.

D. Harel and Y. Koren, "A Fats Multi-Scale Method for Drawing Large Graphs", Journal of Graph Algorithms and Applications 6 (2002), 179-202.

D. Harel and Y. Koren, "Graph Drawing by High-Dimensional Embedding", Proc. Graph Drawing 2002, LNCS 2528, pp. 207-219, Springer-Verlag, 2002.

Y. Koren, L. Carmel and D. Harel, "ACE: A Fats Multiscale Eigenvectors Computation for Drawing Huge Graphs", Proc. IEEE Informatio Visualization (InfoVis '02), IEEE, pp. 137-144, 2002.

Y. Koren and D. Harel, "One-Dimensional Graph Drawing: Part I - Drawing Graphs by Axis Separation", Technical report MCS03-08, Faculty of Math. and Computer Science, The Weizmann Institute of Science, 2003.

Y. Koren, "Graph Drawing by Subspace Optimization", to be published.

T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters 31 (1989), 7-15.

J. W. Sammon, "A Nonlinear Mapping for Data Structure Analysis", IEEE Trans. on Computers 18 (1969), 401-409.