Readings 14: Graphs

in All Readings

There are four required “readings” for graphs (one is a video).

Because I want you to focus on the project, I am reducing the amount of reading. And while the Munzer lecture is really useful (I required it in all past years), I think you can get the main points quickly by skimming through her slides.

Graph layout is a really interesting computational topic, but just reading about it may not be the most important thing. In practice, we often just used implementations of standard layout algorithms.

If you’re interested in the layout algorithms, they are in the optional readings. Fortunately, they are implemented in various toolkits (although, they are interesting).

  • (required)  Arrange Networks and Trees (Chapter 9 from Munzner’s Visualization Analysis & Design) (Munzner-09-ArrangeNetworks.pdf 0.9mb).

    This will get the basic ideas across.

  • (required)  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.

    Looking at this will help you get a sense of the range of opportunities.

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

    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 long 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.

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

    This is an intimidating, long survey. Just skim over it to get a sense of the range of solutions. It is really good at pointing out the basic algorithms.

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.

  • (optional)  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:

  • (optional)  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 … The Gibson survey above (under required) is probably better for the basics.

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