It's late, so I don't want to spend a lot of time going into detail, but:

  • David Wood started the day with the best paper talk, on his results on crossing numbers. The key tool is to "blow up" planar graphs by replacing vertices with constant sized cliques and edges by constant sized bicliques, and then take minors. Let \( P(k) \) denote the family of \( n \)-vertex graphs that are minors of \( k \)-blowups of \( n \)-vertex planar graphs; then he showed that any minor-closed family is a subset of some \( P(k) \), and that a bounded degree graph has linear crossing number if and only if it's in some \( P(k) \) (with \( k \) depending on the constant of linearity and the degree). Therefore, bounded degree graphs excluding a fixed minor have linear crossing number. I'm probably not doing the results justice so go read the paper.

  • Helen Purchase gave a nice talk on usability studies for graph animations. I would like to see more work like this; it's good to see some grounding for all our theory.

  • Oliver Deussen gave an invited presentation with many beautiful computer-generated plant pictures, including some amazing 3d watercolor non-photorealistic renderings.

  • We had a very pleasant banquet filled with too much good food of too many different types at the city palace, not letting out until around midnight.

  • Oh, and I gave two back-to-back talks, on drawing learning spaces and selecting colors for vertices in graph drawings. The color one seems likely to have many other possible applications, for instance for coloring lines in metro map layout (the subject of the other two talks in the same session) and I heard later from Ulrik Brandes some very interesting ideas about using spectral methods for the color choice.




Comments:

None: selecting colors ...
2006-09-28T11:23:15Z

Couldn't you use semidefinite programming to embed a graph in a color space ? In poly time you can embed the vertices in a n-dimensional sphere such that adjacent vertices are far away from each other (the first step of the Goemans-Williamson algorithm for maxcut), then maybe by projecting on a (random ? principal axes ?) 3-dimensional space you can obtain an optimality guarantee on the result. This might be related to the spectral methods you mention.

11011110: Re: selecting colors ...
2006-09-28T16:18:13Z
Maybe. But the detailed shape of color space is relevant (a parallelepiped for RGB, something rather more complicated for Lab). It's important to generate colors that take advantage of the whole gamut and are well spaced throughout it, and I don't immediately see how to guarantee that by methods such as you describe. The eigenvector approach that Brandes suggested at least has the advantage that it can immediately generate points in a parallelepiped, by picking three of the eigenvectors as coordinates).