Graph Drawing, day 2

Quote of the day: Günter Ziegler, as reported by Ileana Streinu at dinner: "money alone doesn't make one unhappy".

Most intriguing talk of the day, for me: Energy-Based Clustering of Graphs with Nonuniform Degrees, by Andreas Noack. The idea is very simple: use a force-based system to move vertices in a graph drawing around (as many other systems already do), but with an attractive force on each edge proportional to its length and its weight, and a repulsive force on each pair of vertices proportional to the logarithm of their distances times the product of the degrees of the two vertices. It's this degree-based weighting in the repulsive force that's the new idea. The problem it fixes is that, without the weights, the forces tend to pull all the high degree vertices together into a big blob in the center, with the low degree vertices scattered around the periphery, which doesn't tell you much about the graph structure. Noack's new weighting lets the high degree vertices float more freely among the other ones, and the resulting drawings show interesting clustering and geographic structure. E.g., he drew a graph of countries with edge weight being strength of economic ties, and it was grouped roughly by continent (North America, Europe, and Asia) and more finely within the continents (Spain next to Portugal). He drew a graph of unweighted edges describing air connections within the US, and even with such a noisy information source the vertices ended up in positions recognizably corresponding to their geography.

George Robertson's talk on interactive hierarchy visualization tools was also very interesting and well received. It's good to see more ties between the information visualization and graph drawing communities, who seem to have much less communication than would be expected from the amount of overlap in their interests.

Comments: