Layout with Circular and Other Non-linear Constraints Using Procrustes Projection

Dwyer, Tim and Robertson, George (2010) Layout with Circular and Other Non-linear Constraints Using Procrustes Projection. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 393-404 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_37).

Full text not available from this repository.

Abstract

Recent work on constrained graph layout has involved projection of simple two-variable linear equality and inequality constraints in the context of majorization or gradient-projection based optimization. While useful classes of containment, alignment and rectangular non-overlap constraints could be built using this framework, a severe limitation was that the layout used an axis-separation approach such that all constraints had to be axis aligned. In this paper we use techniques from Procrustes Analysis to extend the gradient-projection approach to useful types of non-linear constraints. The constraints require subgraphs to be locally fixed into various geometries—such as circular cycles or local layout obtained by a combinatorial algorithm (e.g. orthogonal or layered-directed)—but then allow these sub-graph geometries to be integrated into a larger layout through translation, rotation and scaling.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_37
Classifications:M Methods > M.100 Algebraic
M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.560 Geometry
ID Code:1082

Repository Staff Only: item control page

References

Baur, M., Brandes, U.: Multi-circular layout of micro/macro graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 255–267. Springer, Heidelberg (2008)

Becker, M.Y., Rojas, I.: A graph layout algorithm for drawing metabolic pathways. Bioinformatics 17(5), 461–467 (2001)

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

Borg, I., Groenen, P.J.F.: Modern Multidimensional Scaling: Theory and Applications, 2nd edn. Springer, Heidelberg (2005)

Dwyer, T.: Scalable, versatile and simple constrained graph layout. In: Proc. Eurographics/IEEE-VGTC Symp. on Visualization (Eurovis 2009). IEEE, Los Alamitos (2009) (to appear)

Dwyer, T., Koren, Y., Marriott, K.: Drawing directed graphs using quadratic programming. IEEE Transactions on Visualization and Computer Graphics 12(4), 536–548 (2006)

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

Dwyer, T., Marriott, K., Schreiber, F., Stuckey, P.J., Woodward, M., Wybrow, M.: Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Transactions on Visualization and Computer Graphics 14(6), 1293– 1300 (2008)

Dwyer, T., Marriott, K., Stuckey, P.: Fast node overlap removal. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 153–164. Springer, Heidelberg (2006)

Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 8–19. Springer, Heidelberg (2007)

Dwyer, T., Marriott, K., Wybrow, M.: Dunnart: A constraint-based network diagram authoring tool. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 420–431. Springer, Heidelberg (2009)

Dwyer, T., Marriott, K., Wybrow, M.: Topology preserving constrained graph layout. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 230–241. Springer, Heidelberg (2009)

Everson, R.: Orthogonal, but not orthonormal, procrustes problems. Advances in Computational Mathematics (submitted) (1998), http://secamlocal.ex.ac.uk/people/staff/reverson/uploads/Site/ procrustes.pdf

Friedrich, C., Eades, P.: Graph drawing in motion. Graph Algorithms and Applications 6(3), 353–370 (2002)

Hu, Y.: Efficient and high quality force-directed graph drawing. The Mathematica Journal 10(1), 37–71 (2005)

Jakobsen, T.: Advanced character physics. In: San Jose Games Developers’ Conference (2001),http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml

Lauther, U.: Multipole-based force approximation revisited - a simple but fast implementation using a dynamized enclosing-circle-enhanced k-d-tree. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 20–29. Springer, Heidelberg (2007)

Müller, M., Heidelberger, B., Hennix, M., Ratcliff, J.: Position based dynamics. In: Proc. of Virtual Reality Interactions and Physical Simulations (VRIPhys), pp. 71–80 (2006)

Six, J.M., Tollis, I.G.: A framework for user-grouped circular drawings. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 135–146. Springer, Heidelberg (2004)