| Introduction | Layouts | Program | Image Gallery | Movie Gallery |
We discuss and implement three different algorithms for laying out a series of graphs. Each layout algorithm attempts to come up with a layout for each graph such that the individual layout for each graph is clear while providing some sort of relationship between all the layouts as to create a mental map between the different relationships represented by each graph. Depending on the number of graphs being embedded and the similarity between the individual graphs, different layout algorithms are ideal.
The Aggregate Layout Algorithm creates an aggregate graph which contains one vertex that represents all corresponding vertices from all the graphs. Consequently, each vertex in the aggregate graph represents one or more vertices from the graph sequence, depending on how many graphs that vertex shows up in. The edge set of the aggregate graph is the union of all the edge sets for the graph series. Consequently, there may exist multiple edges from one vertex to another. The aggregate graph is node-weighted and edge-weighted, where the node weight corresponds to the number of times a particular vertex appears in the sequence, and the edge weight corresponds to to the number of times a particular edge appears in the sequence. A modified force-directed approach is then used to layout the aggregate graph, taking into account the weights of the nodes and the edges.
Much like the Aggregate Layout Algorithm, the Merged Layout Algorithm creates a large graph, called a merged graph, and uses a modified force-directed approach to layout the series of graphs. But unlike the aggregate graph created by the Aggregate Layout Algorithm, the merged graph contains a unique vertex for every single vertex that appears in the series. In other words, the number of vertices in the merged graph is the sum of the number of vertices from each graph in the graph series. The edge set of the merged graph also contains all of the edges in the series of graphs. Since every vertex is unique, every edge is also unique. The merged graph's edge set also has a new set of edges. These edges connect corresponding vertices between graphs. The Merged Layout algorithm and implementation allows the user to choose the edge weight of this new set of edges. The larger the weight of these edges the closer the corresponding vertices in each separate layout will be. The final layout of the graphs will put corresponding vertices from each graph relatively close to each other, but unlike the Aggregate Layout Algorithm, they will not have the exact same position.
Our final layout method, the Converging Iterations Layout Algorithm, is quite different than the other two methods. While this algorithm would work for any number of graphs, our implementation works for two graphs but it can be extended to handle more graphs. Unlike the Aggregate Layout Algorithm and the Merged Layout Algorithm, this algorithm does not create a global graph and extract individual layout of each graph from the global layout. Instead this algorithm, first computes initial good placement of both graphs, which we will call G1 and G2, using intelligent placement of vertices, based on the graph distance. Then the algorithm uses the placement for G1, as the initial placement for G2. Similarly, G2's good placement is used as initial placement for G1. Now we use force-directed placement on each graph and obtain our new good placement of each graph. Then we repeat the process until the graphs converge to a some desirable minimum distance.
We discuss and implement three different techniques for viewing multiple graphs. Each visualization scheme attempts to illustrate the series of graphs in such a way to preserve both the individual mental map for each graph and the mental map between all the graph layouts. Each visualization technique corresponds closely with a layout algorithm, but any combination of a layout algorithm and a visualization scheme can be used. The order that the visualization schemes are presented here corresponds to the order of the layout algorithms above.
Using the aggregate view model, each vertex is displayed only once, even though it may appear in multiple graphs. The edges from all the graphs in the sequence are drawn. We use different edge colors and edge styles to differentiate between the different graphs. Displaying all graphs using a single vertex set allows the viewer to see multiple graphs at the same time and view the difference in relationships more easily. This visualization technique corresponds very closely to the Aggregate Layout Algorithm because that algorithm gives corresponding vertices from different graphs the same exact location.
In this visualization scheme each of the graphs is drawn on its separate 2D plane, and the planes are layered in 3D in the order of appearance. By focusing on a single plane, the viewer can easily visualize each individual graph. If the vertices from each graph have relatively close proximity or the same location to corresponding vertices in the other graphs, this visualization scheme illustrates a mental map between all the different graphs. This property makes this visualization technique correspond closely to the Merged Layout Algorithm.
This visualization scheme corresponds to the Converging Iterations Layout Algorithm. Using the split view model, the two graphs are drawn separately in their own windows in 2-dimensions and both windows are on the same screen. The view model can be generalized to handle many graphs, in which case the screen would be split into many individual panes. While there can be any number of graphs displayed in such a way, as the number of graphs being visualized increases, the user's ability to read the relation between them greatly decreases.