Graphs and Trees
From Visualization Sp06
Lecture on Feb 21, 2006
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)
- 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]
- To Draw A Tree. Pat Hanrahan. October 2001. (pdf)
Optional Readings
- Improving Walker's Algorithm to Run in Linear Time. Buchheim, Jünger, and Leipert. Graph Drawing 2002. (link)
- Treemaps for space-constrained visualization of hierarchies. Ben Shneiderman. 1998-2005. (pdf)
- Vizster: Visualizing Online Social Networks. Jeffrey Heer, danah boyd. InfoVis 2005. (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
- Prefuse Application Gallery
- Visual Complexity - graph visualization gallery
Software
- GraphViz - popular graph layout package
- Tulip - a C++ library for large graph layout and visualization
- Java Universal Network/Graph Framework - Java graph processing and visualization library
- prefuse visualization toolkit - Java information visualization toolkit supporting interactive visualization of graphs and trees
Todd - Feb 20, 2006 09:05:19 pm
I find the notion of a circle whose circumference expands exponentially with respect to radius to be fascinating. Unfortunately, the short paper in our suggested readings doesn't go into the details, and its references don't look promising.
Does anyone know of a good reference to something that clearly explains the underlying mathematics of the hyperbolic plane and the Poincare projection?
Jheer - Feb 21, 2006 08:36:58 am
Todd, this journal article has all the details of the layout and projection. Let me know if you have trouble finding it, I have a PDF copy archived on one of my machines...
John Lamping, Ramana Rao: The Hyperbolic Browser: A Focus + Context Technique for Visualizing Large Hierarchies. J. Vis. Lang. Comput. 7(1): 33-55 (1996)
Bryan - Feb 21, 2006 09:57:20 am
A little shameless plug here for a phylogenetic tree visualization my brother worked on: Mesquite. This was probably my first exposure to attempts at visualizing very large data sets. He used the popular moving least squares error minimization techniquet to layout leaves, which seems common now as an approach to graph visualization.
Gwyu - Feb 22, 2006 01:08:13 am
Hyperbolic trees have also been used for more storytelling/artistic purposes, like with the Hyperbolic Reader, which represents explorable spaces of a cartoon story as nodes in a tree. The reader was part of a PARC project on "eXperiments in Future Reading." I think it's an interesting way of presenting a choose-your-adventure story. This got me thinking about other info-vis techniques that have been used for artsy applications. For example, Martin Wattenberg has a section of his site about artsy visualizations. I'm wondering what else people have seen.
Pushkar - Feb 22, 2006 01:29:27 pm
In class, Jeff made the point that just because something was cool visually, it wasn't necessarily useful for data analysis (e.g. the 3D chart from PARC). While I agree with that idea, it's also clear that better visualizations (which typically take longer to generate) can show data trends and patterns that were not obvious before.
So I was wondering if there are any conclusive studies that show when spending the extra effort to generate better visualizations is worth it? Does it depend on the complexity of the data? In other words, how would one convince one's boss that they should spend more money and time on better visualizations, because it will pay off in the long run?
Ashley - Feb 22, 2006 05:45:05 pm
In class, I liked the demo of the radial graph view of the friendster network, but I had some trouble tracking the movement of the nodes as the graph shifted around -- When you choose a new person to be the center of the visualization, the rest of the nodes shift around as well. Sometimes nodes ended up far away from their original position, and I noticed that it sometimes took a bit of time to have to re-find certain names. If the graph were any denser, it seems like this would be even more of a problem. Do you think that highlighting names or sets of names before and after a move would help a viewer at least start looking in the correct area of the graph?
Cynbot - Feb 23, 2006 01:54:34 pm
I looked at Martin Wattenberg's Shape of a Song visualization for a while. I think it is an interesting start at looking at the structure of music. One could just look at the MIDI file in a sequencer and get the same information as what they are plotting. It would be cooler if it worked in real-time, i.e. sending MIDI to their UI and then having it interpret on the fly when to make an arc. I would appreciate any more pointers like this if anyone has them....
Todd - Feb 23, 2006 02:19:00 pm
I found a link to the hyperbolic tree paper. I don't know whether or not this works if you are not on campus.
Brien - Feb 23, 2006 05:49:06 pm
I like force directed layouts. There's a "Bonnie & Clyde" feeling to them about just letting loose and seeing where the layout goes. It seems as if they are in many ways superior to heuristic based layouts. What are the situations in which force directed layouts are substantially worse than heuristic layouts?
Gwyu- these artistic applications are indeed cool. Jeff told me about the Processing exhibit some time ago, and I've been checking back ever since! I recommend it. One of my favorites is http://flight404.com/vj/exhibit.html, which is a visualization to match some 8-bit sounds (by Bit Shifter). It seems it has more to do with color than anything else, although I think it's also about visualizing the dynamics of the music, like rhythm. So size and orientation get played around with among other techniques. Also, in the Pad++ demo available for download, there is some interactive poetry. The words are floating in the zoomable space (I think with images), allowing the user to explore their shape and relation.
AaronHoover - Feb 24, 2006 08:50:44 am
This is maybe somewhat off topic, but also at least partly related to Pushkar's question. A friend of mine told me about this website Gapminder whose goal is to use statistical data and visualization software to present interactive information about world development. From the "About" page - "Gapminder is a non-profit venture for development and provision of free software that visualise human development." There are some pretty interesting interactive presentations of information on GDP, health, and population for a bunch of regions in the world. With regard to Pushkar's question, I think this is one area where the "cool" factor certainly has a valuable impact. I think the interactive and entertaining nature of the presentations really draws the user in and encourages him/her to think more about what the data represent. It's certainly more effective than basic tables or bar charts in my opinion.
Jheer - Feb 24, 2006 06:17:35 pm
Along those lines, both danah boyd and myself (with the Vizster social networking visualization) and Martin Wattenberg (with his NameVoyager visualization) have seen interesting patterns in the playful and social use of visualization technologies. Wattenberg wrote about his observations in a InfoVis 2005 paper (you'll need to go through a campus computer to access this), and I brainstorm some of the design possibilities for fostering and taking advantage of some so-called "coolness" effects in a recent CHI workshop paper. As you note, getting people interested in a particular data set to the point that they want to explore it themselves can be an important achievement.
Of course, this is now officially off-topic for a conversation on graphs and trees!
Yi-Tao - Feb 25, 2006 03:48:19 pm
Even after reading the article, I'm uncertain how useful hyperbolic trees are. It seems that they can easily become too cluttered. As you traverse down the tree, the text for previous nodes dissappear and the context is lost. Also, having the nodes move every time forces the user to become acquainted with a new display (this was even worse when the nodes would rotate).
Cynbot - Feb 25, 2006 06:26:55 pm
Yi-Tao I also felt the same way when we were given the demo, however I would like to see the hyperbolic tree combined with some aggregation near the edges, like the translucent semi-circles in the assigned reading to see if that helps clear up space.
IvanTam - Feb 27, 2006 10:06:33 am
Yi-Tao, Cynbot: Hyperbolic tree seem to remind me a bit of magnifying lens used to zoom in on table cells. Both help bring a small part of the data into focus, but hyperbolic trees, I think, are less useful than magnifying lens. At least magnifying lens allow you to see where in the larger dataset you are zooming into. The "rolling away" of the larger context in hyperbolic trees makes it difficult navigate the larger tree structure. The only cue as to what part of the tree you are currently viewing is given by tracing the arcs between nodes and following them from the root.
Nchentan - Feb 27, 2006 03:03:35 pm
I agree with Yi-Tao, and Cynbot: I feel that hyperbolic tree seems suitable for interactive artistic visualization, but may not be so useful for presenting data for analysis. The main problem seem to be that the edge of visualization do not convey useful information.
I also played with applets in Martin Wattenberg artsy applications as suggested by Gwyu. The Sand Shrimp applet is really cool. Shamefully, it took me a while to figure out the trick! :)
Sharena - Feb 28, 2006 01:14:21 pm
The Pat Hanrahan presentation To Draw a Tree had a slide that I thought was an interesting idea to bring up. He talked about Metaphors as part of the presentation in drawing trees. This seems very important because though we've see that there are many ways now to draw trees, first you need to see if the metaphor of the tree fits the data and in many cases it can, that is why the tree metaphor has survived this long. But it is an interesting thing to think about making sure the tree is a useful metaphor when presenting the data or using these tools.
