Reading 10: Graphs

by Mike Gleicher on March 16, 2017

Due Date: Part 1: Monday, March 27th (preferably before class); Part 1b, 2 Friday, March 31st (assignment)

3/25 update: because the coming weeks will have design challenges (in fact for this week both the end of Design Challenge 1 and the beginning of Design Challenge 2) are going on, I realize I should adjust the expectations for readings and discussions a bit. Also, based on feedback, I will stop splitting readings and discussion assignment postings after this. 

New requirements: Do readings part 1 (Munzner Ch 9 and TreeVis.net). Then pick any 2 of the other “readings.” (and you can just look at Munzner’s slides, or skim one of the long surveys). You are of course welcome to read more – especially if you’re a computing-oriented student and interested in the cool algorithmic challenges of graph layout.

So far, we’ve been talking about encoding information about individual objects. Now we’ll talk about encoding information about the relationships between them.

The word “graph” here is graph in the mathematical sense: data that described the connection between “nodes.”

One thing that is different about this reading: there are some more technical CS topics. So the reading suggestions are more complicated.

Part 1: Monday, preferably before class. Everyone should do these:

  • Chapter 9 of Munzner (link).
  • Look at treevis.net which redirects to here. There are about a zillion different visualizations of trees. Mainly look at the pictures and appreciate the diversity.

Part 1a: this would have been for Monday – but with break beforehand, I wanted to keep Part 1 light – so do it later in the week if you want. This is now optional (see above)

  • Tamara Munzner. 15 Views of a Node-Link Graph: An InfoVis Portfolio google06:Google TechTalks, Mountain View CA, 6/06 Talk video (Video on YouTube) (slides)
    I think it gets the point across that there are lots of design choices and options. Plus, you’ll get a sense of the person behind the book (although, this was almost a decade ago). But, sitting through the hour is a bit much – so it’s OK to just watch a little bit and read through the slides.

Part 2: (for later in the week) The idea was to focus on graph layout. This is a place where we could get some depth into graphs. Except that not everyone has enough background for the deep dive into graph layout algorithms (and it is a really deep topic, with a lot of theory and algorithms, a lot of practical stuff, and even some HCI/perception stuff). And there are many different aspects to this – far more than for a single reading. And, there are other things going on with the Design Challenges, so I’ll require less than last time.

If you’re computationally minded, you should look at the following two things (you can look at things in the other list as well)

  • Scalable, Versatile and Simple Constrained Graph Layout. Tim Dwyer. EuroVis 2009. (pdf)
    It’s a modern take on graph layout. the method gives a sense of the evolution and all the methods that came before it). This might be a little too CS-technical for most people. Don’t worry about the details of the algorithms, but get a sense of the kinds of things the best algorithms try to achieve.
    In practice, people usually use simpler algorithms (force-directed layout)
  • von Landesberger, T., Kuijper, A., Schreck, T., Kohlhammer, J., van Wijk, J. J., Fekete, J.-D., & Fellner, D. W. (2011). Visual Analysis of Large Graphs: State-of-the-Art and Future Research Challenges. Computer Graphics Forum, 30(6). doi:10.1111/j.1467-8659.2011.01898.x (official version) (authors’s copy) – This is a rather intimidating survey. Read it to get a sense of what the basic methods are – don’t try to get at all the details and subproblems and … (the Herman et. al. survey below is a less intimidating variant)

These papers are a little less CS technical, and say much less about the “how” and you should read them if you aren’t as focused on the CS technical issues.

  • Ware, Colin, Helen Purchase, Linda Colpoys, and Matthew McGill. “Cognitive Measurements of Graph Aesthetics.” Information Visualization 1, no. 2 (June 1, 2002): 103–10. doi:10.1057/palgrave.ivs.9500013. (official) (author’s version)
    An older paper that provides some initial experiments into what matters when drawing a graph. It’s the first in a long sequence of papers on graph readability, and is a good place to start.
  • Herman, I., Melancon, G., & Marshall, M. S. (2000). Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics, 6(1), 24-43. doi:10.1109/2945.841119 (official IEE Version – free on campus, or use the library’s EZProxy service)
    This is an old survey, but it gets at the core issues really well. It’s a little less intimidating than von Landesberger, but not as current. Look through it to get a sense of the various issues that people consider, don’t worry about the details.

That’s already probably too much reading for the week, and we haven’t even touched on edge bundling, or gotten into any of the practical layout algorithms, or … (so we have adjusted the expectations – see above).

 

Print Friendly, PDF & Email

Previous post:

Next post: