UC Santa Cruz

This paper focuses on graph layouts with constraints using force-directed simulations. Existing graph drawings with constraints include placement of a particular vertex or a group of vertices at a specified location, constraining placement of vertices and edges to specified rows and/or columns. We propose an alternative way of specifying constraints by allowing the user to interactively draw a boundary wherein the graph layout will be constrained. Such boundary constraints may be saved and applied to other graphs as well. In addition, the boundary may be of different topology such as a donut shape, or figure-eight shape, etc. We model these boundaries as a set of additional forces that contribute to the forces acting on graph vertices. Because our proposed approach is force-directed, it can take advantage of optimizations of other force-directed graph layout algorithms. Furthermore, one can utilize the knowledge of the size of the graph to be visualized and the size of the interior of the boundary region to scale the forces appropriately to achieve a uniform distribution of vertices. We tested this idea on several data sets and different boundary constraints.