Graph Layout

From CS294-10 Visualization Sp11

Jump to: navigation, search

Lecture on April 11, 2011




  • Graph Visualization and Navigation in Information Visualization: A Survey. Ivan Herman, Guy Melancon, M. Scott Marshall. IEEE Transactions on Visualization and Computer Graphics, 2000. Just skim this one.(pdf)
  • Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data. Danny Holten. InfoVis 2006. (pdf)
  • Improving Walker's Algorithm to Run in Linear Time. Buchheim, Jünger, and Leipert. Graph Drawing 2002. (pdf)

Optional Readings

  • Dig-cola: Directed graph layout through constrained energy minimization. Tim Dwyer and Yehuda Koren. IEEE InfoVis 2005. (pdf) [Note: This won the best paper award at InfoVis 05.]
  • Vizster: Visualizing Online Social Networks. Jeffrey Heer, danah boyd. InfoVis 2005. (pdf)
  • Visual Exploration of Multivariate Graphs. M. Wattenberg. CHI 2006. (pdf)
  • A Technique for Drawing Directed Graphs. Gansner, Koutsofios, North, Vo. 1993. (pdf) [Note: This covers the DOT algorithm, used by the popular GraphViz package]

Demonstrations / Examples


Sally Ahn - Apr 12, 2011 12:23:36 am

It wasn't until today's lecture that I really noticed that while Windows employ the indentation method for hierarchical file structure, the "as Columns" view mode for the Finder in Macs closely resembles a traditional tree on its side. That is, the children utilize all of the vertical space to the right of its parent, just as in trees, the children utilize all of the horizontal space below its parent. This alleviates the scrolling problem while maintaining legibility of the file names. Of course, this then requires horizontal scrolling, but I think people tend to work around the same depth level, and I've unconsciously adopted this as my preferred mode of viewing files. It was interesting to look at the design from this perspective.

Michael Cohen - Apr 12, 2011 01:37:25 am

I enjoyed the Holten paper, and thought it was a great example of the whole being greater than the sum of the parts when you combine interactivity with other novel techniques. The bundling technique alone offers some assistance in deciphering the higher-level relationships between clusters, but it can also make individual connections laborious or ambiguous to follow all the way through. By allowing the user to transition seamlessly through different degrees of bundling, the system manages to pack in all facets of the relationships about as densely as possible in time & space. It's great to see not only the novel technique (which would have been worthwhile by itself) but also some thought given into how it might integrate with prior techniques that still have strengths.

Krishna - Apr 12, 2011 12:26:52 pm

One criticism of the Reingold-Tilford algorithm for tree layout is that, the layout is optimized solely on the basis of hierarchy and sibling information. In cases when the nodes and edges of the tree have properties associated with them, we may prefer a layout that exploits the relation between the nodes using the values these properties take. For example, the spacing between similar subtrees can be small relative to the spacing between not-so similar subtrees (similarity may be based on some distance measure computed on these properties). For example, the treemap layout exploits this information by sizing the area a node occupies in the layout - although much could be done there as well.

Brandon Liu - Apr 12, 2011 01:24:36 pm

The PivotGraph paper has an interesting approach to experimentation: It tests the new visualization technique on data that the participants are already familiar with. The paper also does a good job explaining design choices behind the layout of edges in the graph. The grid-based approach is a simplification that solves occlusion problems normally encountered with straight edges.

Saung Li - Apr 12, 2011 07:14:27 pm

I think techniques mentioned in the paper on hierarchical edge bundles to be quite fascinating. Bundle-based visualization can help reduce visual clutter and adjusting the beta value for bundling strength can help users examine adjacency edges between nodes. Trying to find relationships between sparsely connected systems can be extremely difficult without bundling due to the clutter of other edges. It would be interesting to add in techniques like generalized selection and zooming to just look at certain parts of the graph. This can be another way of reducing clutter: remove parts that are not related to what users are looking for. As mentioned in the paper, adding in a feature where users can edit the data easily and see the results graphically might help people explore graphical datasets better. Overall I think the techniques mentioned in this paper are quite neat and the graphs generated do look aesthetically pleasing.

Julian Limon - Apr 12, 2011 11:21:20 pm

The Vizster paper was a great example of how ethnographic research can be combined with information visualization techniques to provide meaningful displays that tell a story. I found their process and explanations fascinating.

Moreover, the paper details some graph layout techniques that might be relevant for our final project. It is interesting how they used existing force-directed algorithms to determine the graph layout, but even more interesting is their choice of context versus detail. Heer and boyd intentionally chose to violate Shneiderman’s “overview first, zoom and filter, then details-on-demand” rule and opted for a philosophy of “start with what you know, then grow.” This approach may also work for our final project. We may decide to display only the information that is relevant for the current trace and then let users explore the rest of the graph on demand.

Michael Hsueh - Apr 12, 2011 11:18:59 pm

I really liked the Holten paper on hierarchical edge bundles. Instead of showing enclosure and adjacency relations using separate edges, bundles uses splines to cleverly and seamlessly incorporate both types of information. This technique really increases the density of information packed in per visual element, and does not increase cognitive load too much. Said in another way, I think the visualization does a good job in packing in lots of information while remaining visually simple. Likewise, adjusting bundling strength is a seamless way of adjusting whether to view higher or lower level relationships. I think its great when an effective visualization (in terms of utility) is naturally aesthetically pleasing. The gradient color coding shown in the paper mostly showed caller-callee relationships, but I can imagine other nice uses for color besides encoding dichotomies. Of course, doing so would require careful consideration of clutter, as the paper focused on extensively.

Karl He - Apr 13, 2011 02:37:47 am

The Herman et al paper raises good points about interactivity regarding trees. It is difficult to implement zoom/pan without losing sight of the context of the focused area, yet it is also necessary for sufficiently large graphs which cannot be viewed in detail in entirety. I like the focus solutions involving logical clusters of nodes, which maintain the context that is most likely to be needed.

Dan - Apr 13, 2011 11:18:25 am

The hierarchical edge bundle-based visualization methods in the Holten paper were very cool. Utilizing spline models and knot vectors to solve interesting problems involving ambiguities was fascinating! As Saung mentioned, this method is good for reducing clutter! I thought the visualizations looked really good and contained a good amount of information between the nodes in subtrees. The Walker's algorithm paper seems like a great reference for use in implementing visualizations where you want to draw trees of unbounded degrees.

Matthew Can - Apr 13, 2011 07:12:38 pm

I thought the hyperbolic layout method was an interesting way of scaling up graph layout to large graphs. But still, this runs into problems eventually, since nodes on the edges of the hyperbolic disc shrink exponentially. Node labels quickly become unreadable and the nodes become smaller than a pixel's width. One way to address this problem is to add a panning-style interaction technique to allow the user to drag the graph across the hyperbolic disc, placing different parts under the central focus. This is similar to the distortion techniques we previously discussed.

I'd also like to share some Java and Javascript graph visualization libraries:

Siamak Faridani - Apr 18, 2011 04:45:43 am

I have combined my comments for both lectures in this page (since they share the same reading material)

[add comment]
Personal tools