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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwyer, T., Robertson, G. (2010). Layout with Circular and Other Non-linear Constraints Using Procrustes Projection. In: Eppstein, D., Gansner, E.R. (eds) Graph Drawing. GD 2009. Lecture Notes in Computer Science, vol 5849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11805-0_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-11805-0_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11804-3
Online ISBN: 978-3-642-11805-0
eBook Packages: Computer ScienceComputer Science (R0)