IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs
|
We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data.
[1] 821 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), pp. 125–137.
[2] S. J. Brams, H. Mutlu, and S. L. Ramirez, "Influence in Terrorist Networks: From Undirected To Directed Graphs", Studies in Conflict and Terrorism 29 (7), Taylor and Francis (to appear 2006).
[3] T. Dwyer and Y. Koren, "Dig-CoLa: Directed Graph Layout through Constrained Energy Minimization", IEEE Symposium on Information Visualization (Infovis'05), (2005), pp. 65–72.
[4] T. Dwyer, Y. Koren, and K. Marriott, "Drawing Directed Graphs Using Quadratic Programming", IEEE Transactions on Visualization and Computer Graphics 12 (4), IEEE (2006), pp. 536–548.
[5] T. Dwyer, Y. Koren, and K. Marriott, "Stress Majorization with Orthogonal Ordering Constraints", Proc. 13th Int. Symp. Graph Drawing (GD'05), LNCS 3843, Springer (2006), pp. 141–152.
[6] T. Dwyer, K. Marriott, and P. J. Stuckey, "Fast Node Overlap Removal", Proc. 13th Int. Symp. Graph Drawing (GD'05), LNCS 3842, Springer (2006), pp. 153–164.
[7] T. Dwyer, K. Marriott, and P. J. Stuckey, "Fast Node Overlap Removal — Addendum", Technical Report, Monash University, http://www.csse.monash.edu.au/~tdwyerFNORAddendum.pdf.
[8] T. Dwyer, K. Marriott, and M. Wybrow, "Integrating Edge Routing into Force-Directed Layout", Proc. 14th Int. Symp. Graph Drawing (GD'06), Springer (to appear 2007).
[9] P. Eades and X. Lin, "A New Heuristic for the Feedback Arc Set Problem", Australian Journal of Combinatorics 12, (1995), pp. 15–26.
[10] M. Eiglsperger, M. Siebenhaller, and M. Kaufmann, "An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing", Journal of Graph Algorithms and Applications 9 (5) (2005), pp. 305–325.
[11] E. Gansner, Y. Koren, and S. North, "Graph Drawing by Stress Majorization", Proc. 12th Int. Symp. Graph Drawing (GD'04), LNCS 3383, Springer (2004), pp. 239–250.
[12] D. Harel and Y. Koren, "Drawing Graphs with Non-uniform Vertices", Proc. Working Conference on Advanced Visual Interfaces (AVI'02), ACM Press (2002), pp. 157–166.
[13] W. He and K. Marriott, "Constrained Graph Layout", Proc. 3rd Int. Symp. Graph Drawing (GD'96), LNCS 1190, Springer (1996), pp. 217–232.
[14] W. He and K. Marriott, "Constrained Graph Layout", Constraints 3 (1998), pp. 289–314.
[15] M.L. Huang and P. Eades, "A Fully Animated Interactive System for Clustering and Navigating Huge Graphs", Proc. 5rd Int. Symp. Graph Drawing (GD'98), LNCS 1547, Springer (1998), pp. 374–383
[16] T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters 31 (1989), pp. 7–15.
[17] K. Misue, P. Eades, W. Lai, and K. Sugiyama, "Layout Adjustment and the Mental Map", Journal of Visual Languages and Computing 6 (1995), pp. 183–210.
[18] Mosek Optimization Toolkit V3.2 www.mosek.com.
[19] J. Nocedal and S. Wright, Numerical Optimization, Springer (1999).
[20] 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), pp. 97–104.
[21] K. Sugiyama, S. Tagawa, and M. Toda, "Methods for Visual Understanding of Hierarchical Systems", IEEE Trans. Systems, Man, and Cybernetics 11 (1981), pp. 109–125.
[22] X. Wang and I. Miyamoto, "Generating Customized Layouts", Proc. 2nd Int. Symp. Graph Drawing (GD'95), LNCS 1027, pp. 504–515.
Index Terms:
Graph drawing, layout, constraints, stress majorization, force directed algorithms,multidimensional scaling.
Citation:
Tim Dwyer, Yehuda Koren, Kim Marriott, "IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 821-828, Sept. 2006, doi:10.1109/TVCG.2006.156
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb