Graphs and Trees

From CS294-10 Visualization Fa07

Jump to: navigation, search

Lecture on Oct 1, 2007



[edit] Readings

  • Graph Visualization and Navigation in Information Visualization: A Survey. Ivan Herman, Guy Melancon, M. Scott Marshall. IEEE Transactions on Visualization and Computer Graphics, 2000. (pdf)
  • Improving Walker's Algorithm to Run in Linear Time. Buchheim, J√ľnger, and Leipert. Graph Drawing 2002. (link)
  • To Draw A Tree. Pat Hanrahan. October 2001. (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.]
  • Treemaps for space-constrained visualization of hierarchies. Ben Shneiderman. 1998-2005. (pdf)
  • Vizster: Visualizing Online Social Networks. Jeffrey Heer, danah boyd. InfoVis 2005. (pdf)
  • Visual Exploration of Multivariate Graphs. M. Wattenberg. CHI 2006. pdf
  • Laying out and visualizing large trees using a hyperbolic space. John Lamping, Ramano Rao. UIST 1994. (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


[edit] Hazel Onsrud - Sep 29, 2007 06:20:37 pm

One of the noted issues in Graph Visualization and Navigation in Information Visualization: a Survey concerned the size of the graph and this immediately struck me as a very good example of a property on which computer software has a great impact. Being able to zoom in or out on graphs, whether in a controlled or uncontrolled manner (albeit there are benefits and drawbacks to both) is an attribute that at least I took for granted, but is actually a fantastic development, facilitating ease of understanding and exploration of the graphics.

[edit] Ken-ichi - Sep 30, 2007 04:11:07 pm

One of my favorite interactive tree browsers was shown in the introduction video for the Encyclopedia of Life project. The video was put together by a design agency, and most of the stuff shown is (I assume) pure vapor, but they have a really cool-looking tree viewer that uses perspective to focus attention on a given level of hierarchy. The level of the tree you're examining seems larger (and has more detail) than levels further up, which seem distant. I like it because instead of the unnatural distortions you get in a fish-eye display, this takes advantage of the very natural perception of single-point perspective. I guess it's also sort of like semantic zooming, in that the focus level has a lot more (not just bigger) information than levels further back. Here's a pic:


[edit] Mark Howison - Sep 30, 2007 08:59:52 pm

I'm not sure that I agree with Herman, Melancon & Marshall's claim that cognitive science findings have few practical applications for visualization. Granted, much of cognitive science has been focused on areas like AI and human endeavors such as learning and language. However, as far as general findings on perception, the field is much richer than the two dated examples mentioned by Herman, Melancon & Marshall: information overload and Gestalt principles. There is plenty of modern research in areas like mental imagery (Kosslyn, Shepard, Parsons), distributed cognition (Pea, Hutchins, Norman), and socio-historic views on perception (especially Steven and Hall's work on "disciplined perception") that could inform design principles for visualization. The difference is that these results are more context-specific. That is, Gestalt principles can provide decontextualized design principles that apply to all visuals. Applying more recent research in perception/imagery/cognition will likely be contextualized by the data domain being visualized, users' actions and goals, and the role the visualization plays in users' conceptual change.

[edit] Wesley Willett - Sep 30, 2007 11:49:39 pm

In Graph Visualization and Navigation in Information Visualization: a Survey, I've noticed that the discussion of layout and interaction seems primarily concerned with the positioning of nodes, with a few constraints (namely edge crossings) placed on the edges of the graph. However, it occurs to me that there are a number of situations in which handling the layout and routing of the edges is potentially more important than that of the nodes. This includes graph variants like flow maps and other graphs in which nodes already have real geo-spatial positions (things like abstracted subway or highway maps) but need to be considered in concert with additional constraints on the edges (smoothness, orientation, alignment, geometry, length).

I imagine there is an entire class of tree layout problems in which the relative positions of the nodes are unimportant, but in which the size, length, and other properties of the edges that connect them take precedence and should determine the graph's shape. It's unclear to me on first inspection how many of the techniques described in the paper (with the exception of force-directed layout) are applicable to these sorts of graphs. Thoughts?

[edit] N8agrin - Oct 01, 2007 09:17:18 am

Wes, I agree with your comment about edge focused algorithms, and think that nodes may not always be the primary unit of interest in a tree-based visualization.

Melancon and Marshall make it clear that minimizing the amount of data visible in trees aids the viewer in interpreting the overall information presented, regardless of the format of the tree structure. They discuss clustering as one method of reducing the amount of data visible, and I wonder if the power of clustering is rooted in its mirroring of the way we mentally scaffold information. Clustering suggests the need for further interactive techniques, however, to ensure the viewer does not become lost navigating not only the hierarchical structure of the tree, but also the depth of the cluster.

I'm not sure I agree with Melancon and Marshall's general description of 3d cone graphs. They clearly state that 3d tree graphs have their own associated problems, but they present cone graphs in a seemingly better light. I'm not sure that any 3d visualization of tree data provides a better metaphor for traversing the structure. It would seem that the primary purpose of iterating through a tree would be to retain the context of what each parent node, or previous node visited was. In the case of 3d models, such as SGI's file browser, I can't see how a larger visualization that excludes the majority of data from the view is really beneficial.

The limited amount of information displayed in 3d models contrasts with the vast amount of information that can be encoded in 2d models. This suggests to me that there is an optimal amount of information that can be displayed, which is neither overtly minimalistic nor excessive, but rather depends upon the nature of the information within the tree structure.

[edit] Karen Hsu - Oct 02, 2007 09:40:07 pm

I can't help but be reminded of the Rate My Network Diagram website. As the name suggests, it's a social rating site where users can rate the aesthetics and effectiveness of user-submitted network diagrams.

[edit] Daisy Wang - Oct 03, 2007 11:46:11 am

Is there any default visualization layout for hierarchical graph, allowing zooming?

My definition of hierarchical graph has N (N>=1) levels. A node in level M (2,...,N), represents a set of nodes in level (M-1) and their internal edges. Two nodes, {M_i, M_j} in level M has an edge, if and only if exists a pair of nodes they represent in lower levels, has an edge aross the node set.

For example, a hierarchical graph can have bayesian network at the ground level, and the junction tree at the second level. Any nodes in the junction represents one or multiple nodes in the ground bayesian network.

I suppose this should be able to implemented by extending the radial graph view in perfuse.

[edit] Robin Held - Oct 04, 2007 03:13:14 pm

I've always found binary trees to be an interesting topic in computer science. The algorithms that have been written to traverse them, both for data input/output and for display, seem very clean and concise. I also like how prefuse offers a wider range of visualization options with an interactive element. Specifically, when data sets become more complicated than binary trees, it seems logical to provide users with a set of powerful tools that can be used to create custom graphics. As I mention in my comments for the October 3rd lecture, I strongly believe it's important to allow (or sometimes require) human input when a visualization's quality becomes increasingly subjective.

[edit] Amanda Alvarez - Oct 06, 2007 08:40:39 pm

When the Reingold-Tilford algorithm goes from up from child to parent and across, laying out the graph, how does it know which nodes belong at the same level? Is this information just assumed to be built in to the data from which the tree is built?

There did not seem to be much in the readings about how the underlying data inform and constrain the graph layout, other than the structured/unstructured distinction (do they lend themselves to graphs or not at all), and the discussion of how size leads to zooming. There are inherent relations and hierarchies in the data, but couldn't you tweak it to conform to a particular layout? (or is this just a waste of time because this is what the 'interaction' part should be letting you do.) Seems like to make the clearest graph, you have to already know what is there (nothing unexpected will pop out anyway since the data are already constrained, eg. a long lost cousin is not going to appear in the family genealogy). What I mean is that graph construction seems to be a post-hoc thing, maybe more about documentation or finalizing the results of a complex process; it's not about poking around the data and finding new insights (in the sense that Assignment 2 was). Not entirely sure to what extent graphs/trees should be considered 'special' cases. True, the underlying data are more structured than a mass of randomness you insert into Tableau, but you use the same techniques to build them as for other visualizations, and the end goal is roughly the same (if not decision making, some sort of 'finalization' at least).

Tangential trip into the past. Jurassic Park and Unix (FSN GUI) circa 1993.

Image:jurassic01.jpg Image:jurassic02.jpg


[edit] David Jacobs - Oct 07, 2007 11:45:52 pm

Daisy: I'm not sure I completely understand your definition of a heirarchical graph. Is it some kind of tree-like thing where as you go higher up in the tree, more and more nodes are merged into their parents? Or is this a set of N disconnected graphs each representing the same data, but at different levels of detail (how many leaf nodes are represented by a single intermediate node at level M). In any case, I can't imagine there being a good algorithm for generating nice layouts for general graphs. For some graph relationships, it's impossible to plot them without any edges crossing (consider a clique of size greater than 4). I'm betting there are tricks to minimize edge crossings, or make them less significant (like line hops or shading), but making a good default layout algorithm is probably not trivial.

[edit] James Andrews - Oct 08, 2007 02:49:50 am

David -- I think that the physics (force) based graph layouts are pretty generally applicable to any graph structure. Of course there are still problems for any graph visualizer (like the clique issue you mentioned) and you could certainly have an overwhelming amount of data that demands its own context-sensitive solution, but as an easy general solution force directed layouts still seem quite powerful. For Daisy's hierarchical graph, for example -- if you think of it as being a compacted graph but with the ability to expand any node of the graph into a more detailed multi-node representation (or to conversely re-compact), then a physics based model might be really nice since the expansion and contraction process could be naturally animated and constructed without having to worry about generating special new algorithms for reconfiguring the graph on the fly. Or, to display all levels of detail at once, you can imagine a sort of treemap metaphor, where one draws low-detail nodes as very large, shaded circles which contain within the structure of the high detail nodes; it seems this could also be done in the physics system just by adding a force constraining the nodes to by grouped inside their super-nodes.

I'm not sure how extending the radial graphs would work well for the hierarchical graphs -- I see how you could represent a hierarchy in a radial tree structure, but how do you connect nodes on opposite sides of the circle without it getting confusing?

[add comment]
Personal tools