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 , pp. 393-404(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item