After the final day of Graph Drawing, the conference organizers arranged a guided tour for us at ZKM, a large modern art museum in Karlsruhe with a big exhibit of algorithmic and interactive art, and what they told us was the world's oldest continuously-operating computer, originally built using vacuum tubes by Konrad Zuse. Definitely worth a visit — I would have liked a lot more time to browse the exhibits.

Several of today's talks were a bit of a blast from the past for me, discussing results related to geometric thickness and confluent drawing.

( Read more... )

Via placemap: Flow Map Layout, Phan et al., InfoVis'05.

The idea seems to be to visually express how much movement there is from different geographically placed sources to a single sink, by drawing the movement as a confluent tree in which physically nearby sources are merged together, and the thickness of a confluent edge indicates the amount of movement along that edge. So it's closely related to confluent graph drawing, but not the same, because the initial data is not so much a graph as a spatial numeric field (the amount of movement from each site) and the confluent tracks merge but don't unmerge. However, there is some graph drawing involved, in placing the edges and merge nodes of the resulting tree so that it doesn't cross itself.

The journal version of Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way (with M. Dickerson, M. T. Goodrich and J. Y. Meng) is now available: J. Graph Algorithms and Applications (special issue for GD'03) 9(1):31-52, 2005.

I think most planar graphs, in some sense, should have complements with no confluent drawing, but it's been difficult to prove. Finally, I think I've found an example: the gyroelongated square dipyramid, shown below in two drawings. The left is a rough sketch of its form as a polyhedron with equilateral-triangle faces, while the right is a planar drawing.

( Read more... )

Henk Meijer has described the confluent graph whose complement isn't confluent, and it's quite simple. In fact, the nonconfluent part was in our first paper on confluence: the Petersen graph, minus a vertex, is nonconfluent because it's nonplanar (a subdivision of K_3,3) and has no 4-cycles, so no way for confluence to gain traction. It turns out that its complement is confluent:

Via Jeff: a confluent drawing of an orientation of the complete graph on 25 vertices. As used to explain a complicated variant of roshambo... We've talked about digraphs as being one of the next directions to take confluent drawing theory, so it's interesting to see such drawings in the wild.

Discovered that Google Blog Search generates RSS feeds for its results. Which in retrospect should be very unsurprising, but cool nonetheless. Scanning through one such feed, I found that phenyx is another graph drawer, with a much more detailed set of diary entries from the conference than mine. Including one mentioning delta-confluence; good to see someone was paying attention... Hi, Sebastian, whoever you really are.

Slides from my Graph Drawing talk, Delta-Confluent Drawings, are now online here.

I think the talk went well; at least, I got plenty of good questions and feedback about it. The last-minute decision to add a confluent H-tree drawing of K₁₂₈ (I had the rest of the slides ready a month ago) seems to have been a good one, since a lot of people seem to have been impressed by how such a dense graph could be made to look so uncluttered. Seok-Hee Hong asked about the possibility of three-dimensional confluent drawing; obviously, it wouldn't remove crossings, but it could be useful for reducing visual clutter, and I had a brief discussion with someone else about similar confluence-based decluttering of 2-dimensional drawings allowing crossings. Someone (I forget who, sorry) asked about combining clustered drawing with confluence; in fact, we'd been thinking about this after seeing a slide the previous day that appeared to be doing it. It seems like replacing the edges between clusters in a clustered drawing by a single confluent track, even if it loses information about exactly which edges are present, might be a useful visual simplification. David Wood repeated Janos Pach's question about whether confluent graphs are closed under complementation — delta-confluent graphs (aka distance-hereditary graphs) certainly aren't, and by the end of the day I'd heard from multiple sources that confluent graphs in general aren't either, though I still haven't seen the counterexample. But there's enough structure in distance-hereditary graphs that it may be possible to draw their complements confluently if not delta-confluently. Mike Goodrich showed me that our construction for confluent interval graph drawing also works for bipartite convex graphs, but he thinks their complements are not drawable. And Bettina Speckmann and Elena Mumford talked about the possibility of using confluence for flow maps in cartography. So I'm hopeful of seeing a lot more confluent drawing research in the near future.

Just uploaded four newish papers to arxiv. They are:

• The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (with Mike Goodrich and Jonathan Sun, from SoCG'05). Random sampling gives an efficient way of dynamizing quadtrees and performing approximate range queries with them.


• Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets (with Lars Arge and Mike Goodrich, from PODC'05). Distributed versions of tries, skip quadtrees, trapezoidal decompositions, etc.


• Confluent Layered Drawings (with Mike Goodrich and Jeremy Meng, from Graph Drawing '04). A combination of our confluent drawing idea from GD'03 with Sugiyama style layered drawings. This is the paper that the leaning tower of Pisa logo (at right) for SoCG'05 came from.


• Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku. A combination of graph algorithms and rule-based puzzle solving heuristics. I still need to figure out where to send this, maybe another combinatorial games workshop of some sort?

I also heard this week that another confluent drawing paper with Goodrich, Meng, and myself has gotten into GD'05. Good news, because that means Jeremy has enough publications to put together a very coherent thesis. Will upload after responding to referee suggestions.