IPSEP-COLA: an incremental procedure for separation constraint layout of graphs.

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data.

Drawing directed graphs using quadratic programming.

We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes.

Topological fisheye views for visualizing large graphs.

Graph drawing is a basic visualization tool that works well for graphs having up to hundreds of nodes and edges. At greater scale, data density and occlusion problems often negate its effectiveness. Conventional pan-and-zoom, multiscale, and geometric fisheye views are not fully satisfactory solutions to this problem. As an alternative, we propose a topological zooming method. It precomputes a hierarchy of coarsened graphs that are combined on-the-fly into renderings, with the level of detail dependent on distance from one or more foci. A related geometric distortion method yields constant information density displays from these renderings.

Combining hierarchy and energy for drawing directed graphs.

We present an algorithm for drawing directed graphs which is based on rapidly solving a unique one-dimensional optimization problem for each of the axes. The algorithm results in a clear description of the hierarchy structure of the graph. Nodes are not restricted to lie on fixed horizontal layers, resulting in layouts that convey the symmetries of the graph very naturally. The algorithm can be applied without change to cyclic or acyclic digraphs and even to graphs containing both directed and undirected edges. We also derive a hierarchy index from the input digraph, which quantitatively measures its amount of hierarchy.

Robust linear dimensionality reduction.

We present a novel family of data-driven linear transformations, aimed at finding low-dimensional embeddings of multivariate data, in a way that optimally preserves the structure of the data. The well-studied PCA and Fisher's LDA are shown to be special members in this family of transformations, and we demonstrate how to generalize these two methods such as to enhance their performance. Furthermore, our technique is the only one, to the best of our knowledge, that reflects in the resulting embedding both the data coordinates and pairwise relationships between the data elements. Even more so, when information on the clustering (labeling) decomposition of the data is known, this information can also be integrated in the linear transformation, resulting in embeddings that clearly show the separation between the clusters, as well as their internal structure. All of this makes our technique very flexible and powerful, and lets us cope with kinds of data that other techniques fail to describe properly.