Graph Drawing by Subspace Optimization

Abstract

We show a novel approach for accelerating the computation of graph drawing algorithms. The method is based on the notion that we can find a subspace with a relatively low dimensionality that captures the "nice" layouts of the graph. This way each axis of the drawing is a linear combination of a few basis vectors, instead of being an arbitrary vector in Rn (n is the number of nodes). We describe ways of constructing these basis vectors and also algorithms for optimizing the graph drawing in the resulting subspace.