Reading and Discussion 13: Week 13 – Graphs

by gleicherapi on August 1, 2017

Initial Posting Due: Tue, Nov 28 at (Canvas Link)

Readings

Finding appropriate readings is hard. The first two are required:

  • Arrange Networks and Trees (Chapter 9 from Munzner’s Visualization Analysis & Design) (Munzner-09-ArrangeNetworks.pdf 879 kb)
  • 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)

Online Discussion

Initial Posting Due: Tue, Nov 28 at (Canvas Link)

For this week’s discussion prompts, here are two questions that will hopefully help you connect the readings to problems you encounter (like the Design Challenge).

  1. When you look at the treevis.net website, you can see a lot of different ways to represent a tree (which is a special kind of graph). Pick one that you found surprising/weird (at least from the picture, you don’t need to read the paper). What do you think is good/bad about it? Why did you think the author made it? Does the design extend to the more general case of a directed graph?

  2. A node-link diagram is the standard way to show graph data – but it’s clearly note the only one. What are the pros and cons of a node link diagram?

Print Friendly, PDF & Email

Previous post:

Next post: