Constrained Stress Majorization Using Diagonally Scaled Gradient Projection

Dwyer, Tim and Marriott, Kim (2008) Constrained Stress Majorization Using Diagonally Scaled Gradient Projection. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 219-230 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_23).

Full text not available from this repository.

Abstract

Constrained stress majorization is a promising new technique for integrating application specific layout constraints into force-directed graph layout. We significantly improve the speed and convergence properties of the constrained stress-majorization technique for graph layout by employing a diagonal scaling of the stress function. Diagonal scaling requires the active-set quadratic programming solver used in the projection step to be extended to handle separation constraints with scaled variables, i.e. of the form s_i y_i + g_ij le s_j y_j. The changes, although relatively small, are quite subtle and explained in detail.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_23
Classifications:M Methods > M.100 Algebraic
P Styles > P.720 Straight-line
ID Code:841

Repository Staff Only: item control page

References

Fisk, C. J., Isett, D. D.: ACCEL: automated circuit card etching layout. In: DAC'65: Proceedings of the SHARE design automation project, ACM Press (1965) 9.1-9.31

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31 (1989) 7-15

Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Proc. 14th Intl. Symp. Graph Drawing (GD '06). Volume 4372 of Lecture Notes in Computer Science., Springer (2007) 8-19

Dwyer, T., Koren, Y., Mariott, K.: IPSep-CoLa: An incremental procedure for separation constraint layout of graphs. IEEE Transactions on Visualization and Computer Graphics 12 (2006) 821-828

Borg, I., Groenen, P. J.: Modern Multidimensional Scaling: theory and applications. 2nd edn. Springer (2005)

Gansner, E., Koren, Y., North, S.: Graph drawing by stress majorization. In: Proc. 12th Int. Symp. Graph Drawing (GD'04). Volume 3383 of Lecture Notes in Computer Science., Springer (2004) 239-250

Bertsekas, D. P.: Nonlinear Programming. Athena Scientific (1999)

Dwyer, T., Marriott, K.: Constrained stress majorization using diagonally scaled gradient projection. Technical Report 217, Clayton School of IT, Monash University (2007)

os, P. E., Rényi, A.: On random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17-61

Barabási, A. L., Reka, A.: Emergence of scaling in random networks. Science 286 (1999) 509-512