Stress Majorization with Orthogonal Ordering Constraints

Dwyer, Tim and Koren, Yehuda and Marriott, Kim (2006) Stress Majorization with Orthogonal Ordering Constraints. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 141-152 (Official URL:

Full text not available from this repository.


The adoption of the stress-majorization method from multi-dimensional scaling into graph layout has provided an improved mathematical basis and better convergence properties for so-called ``force-directed placement`` techniques. In this paper we give an algorithm for augmenting such stress-majorization techniques with orthogonal ordering constraints and we demonstrate several graph-drawing applications where this class of constraints can be very useful.

Item Type:Conference Paper
Additional Information:10.1007/11618058_14
Classifications:M Methods > M.999 Others
M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.140 Augmentation
ID Code:717

Repository Staff Only: item control page


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

R. Boisvert, R. Pozo, K. Remington, R. Barrett and J. Dongarra, "The Matrix Market: A web resource for test matrix collections", in Quality of Numerical Software, Assessment and Enhancement, Chapman Hall (1997) 125-137.

L. Carmel, D. Harel and Y. Koren, "Combining Hierarchy and Energy for Drawing Directed Graphs", IEEE Trans. Visualization and Computer Graphics 10 (2004) 46-57.

T. Dwyer, Y. Koren and K. Marriott, "Stress Majorization with Orthogonal Ordering Constraints", Technical Report 2005/175, Monash University School of Computer Science and Software Engineering (2005). Available from

T. Dwyer and Y. Koren, "DIG-COLA: Directed Graph Layout through Constrained Energy Minimization", IEEE Symposium on Information Visualization (Infovis'05) (To appear 2005).

E. Gansner, Y. Koren and S. North, "Graph Drawing by Stress Majorization", Proc. 12th Int. Symp. Graph Drawing (GD'04), LNCS 3383, Springer Verlag (2004) 239-250.

W. He and K. Marriott, "Constrained Graph Layout", Constraints 3 (1998) 289-314.

S. Hong, D. Merrick and H. Nascimento, "The metro map layout problem", Proc. 12th Int. Symp. Graph Drawing (GD'04), LNCS 3383, Springer Verlag (2004) 482-491.

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

K. Misue, P. Eades, W. Lai, and K. Sugiyama, "Layout Adjustment and the Mental Map", Journal of Visual Languages and Computing 6 (1995) 183-210.

K. Ryall, J. Marks and S. M. Shieber, "An Interactive Constraint-Based System for Drawing Graphs", ACM Symposium on User Interface Software and Technology (1997) 97-104.

K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual Understanding of Hierarchical Systems", IEEE Trans. Systems, Man, and Cybernetics 11 (1981) 109-125.

J. Nocedal, S. Wright, Numerical Optimization, Springer (1999).

Mosek Optimization Toolkit V3.2