The Week in Vis 13 (Mon, Nov 26 – Fri, Nov 30): Graphs

by Mike Gleicher on November 23, 2018

Class Meetings
  • Mon, Nov 26 – Lecture/ICE:Graphs
  • Wed, Nov 28 – Lecture:Graph Layout
  • Fri, Nov 30 – NO CLASS
Week Deadlines

Hope everyone had a good Thanksgiving.

Last week, we spent a lecture on 3D, and then took a lecture to revisit issues of scaling as a way to think more about Design Challenge 3 (which is going on as we speak).

This week, we’ll talk about graphs – which is a big topic. And one you’ve already seen at least some of for DC2. In fact, The TreeVis.NET web site (which is a required “reading” for this week) was recommended on the DC2 assignment.

On Monday, we’ll talk about graphs in general, and we’ll do a little design puzzle to get us thinking about node link layout. Then on Wednesday we’ll talk more about node-link layout.

You may want to look at this week’s learning goals Learning Goals 13: Week 13 – Graphs.

Readings (due Mon, Nov 26 – preferably before class)

Finding appropriate readings is suprisingly hard.

  • Arrange Networks and Trees (Chapter 9 from Munzner’s Visualization Analysis & Design) (Munzner-09-ArrangeNetworks.pdf 0.9mb)
  • TreeVis.net has a huge number of visualizations of trees. Look at the pictures and try to get a sense of how many different ways there are to do this.

Tamara Munzner gave a talk that gets across the point that there are many ways to show a graph. 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.

  • Tamara Munzner. 15 Views of a Node-Link Graph: An InfoVis Portfolio, Google TechTalks, Mountain View CA, 6/06. Talk video (Video on YouTube) (slides)

I wanted to find a survey paper that covered the more computational aspects (the layout algorithms). I haven’t found one that I like. Instead, I am recommending this paper. Read it to get a sense of what the basic methods are – don’t try to get at all the details and subproblems and …

  • 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)

Optional

There is a lot out there. One good general source for background is the book “Handbook of graph drawing and visualization” – which you can find drafts of the chapters online. In particular, the Chapter on Force-Directed Layout (at least the beginning parts of it) gives a review of the classical algorithms.

  • Kobourov, S. (2016). Force-Directed Drawing Algorithms. In Handbook of Graph Drawing (pp. 383–408). (pdf online)

For a modern algorithm for small to medium graphs:

  • Dwyer, T. (2009). Scalable, Versatile and Simple Constrained Graph Layout. Computer Graphics Forum, 28(3), 991–998. (pdf) (doi)It’s a modern take on graph layout. It considers many aspects about what makes for a good layout, and uses real optimization methods to achieve them. 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)

Previous post:

Next post: