Readings 12: Graphs

in All Readings

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

Note that for numbers 2 and 4 I do not expect you to read/watch the whole thing. Just look through it and get an idea of what the main points are.

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

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

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

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

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

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

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