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

摘要

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.