The Week in Vis 12 (Mon, Nov 18 – Fri, Nov 22): Graphs

by Mike Gleicher on November 15, 2019

Week in Vis 12 Mon, Nov 18-Fri, Nov 22

Last week, we talked about evaluation and wrapped up DC2. That means this week its time for sleep DC3! The DC3 draft is actually on the web, but it’s still a draft – expect an announcement Monday. We’ll talk about it in class on Wednesday.

For DC3 you will be allowed to work with a partner (although, we prefer you pick a partner from another department). If you want help finding a partner, let us know – we can do some match-making. There is nothing due for DC3 on Wednesday, Nov. 20 (other than to tell us if you want to work with a partner).

Note: my office hours are cancelled this week: I will be leaving town after class on Wednesday.

Readings for the Week

Finding appropriate readings is surprisingly 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 also want you to look through a survey on graph drawing. The “required” reading is the Gibson paper. In 2018, I used the vonLandesberger survey paper (optional, below). This paper is still too big a list of too many things (the paper is over 30 pages long – or 60 pages in the double spaces). I do not expect you to read the whole thing. But, skim through it. If you read the first paragraph of each section, you’ll get a sense of the range of things – and if you want a huge list of specific examples, you can read more.

  • Gibson, H., Faith, J., & Vickers, P. (2013). A survey of two-dimensional graph layout techniques for information visualisation. Information Visualization, 12(3–4), 324–357. (doi) (author verson)

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)

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)

Previous post:

Next post: