I just returned from a pleasant post-SoCG visit to Bettina Speckmann in the Netherlands. While there, she presented me with a copy of Metroville, a puzzle based on confluent drawing. (Image below stolen from the manufacturer's web site.)



Metroville consists of a game board with nine rotating pieces on it, each containing a section of train track with turns and junctions. The pieces can be permuted to form eight different "cities", and for each city there are eight puzzles, in which one must rotate the pieces so that the resulting configuration of track can allow a train to pass through a given sequence of cities in order without reversals.

I haven't worked out the details, but I'm pretty sure that larger versions of the game would be NP-complete (that is, it should be NP-complete to test, for a fixed city, whether there exists a set of rotations that allows a given train route to work) by a reduction from 3-SAT very similar to the one in my Phutball paper in which the train zigzags horizontally across the board through tracks representing variables and then zigzags again vertically through tracks representing clauses.

Regardless, it's a fun puzzle. Thanks, Bettina!

Also, slides from Elena Mumford's talk on area-universal cartograms (my SoCG paper with Bettina, Elena, and Bettina's student Kevin Verbeek) are now online.

In the revisions of one of my papers, I needed an illustration of the graph shown below, which comes from an NP-completeness reduction. This is a confluent drawing: two vertices are connected by an edge whenever there is a smooth path between them. (The paths are allowed to self-intersect, so for instance all 30 outer vertices form a clique.)



I think it's a great illustration of the power of confluent graph drawing: the graph has 37 vertices, 536 edges, and an average degree of nearly 29, but despite being so dense the graph has a lot of structure and the drawing makes the structure apparent.

Complexity doesn't have to be ugly: Glyphobet links to dburrows' diagrams of the apt system as an example of why automated graph drawing tools could benefit with interaction from skilled graphic designers.

Beyond Glyphobet's point (which I agree with) I think the drawings could also benefit from some of my own research, on confluent drawing. It's not that the drawing is nonplanar — one benefit of confluence is replacing many crossing single-to-single connections by a single many-to-many connection, reducing the number of crossings, but that isn't an issue in this drawing. Rather, what I think would most improve the drawings (beyond a little more care in vertex placement and edge routing so that unnecessary crossings and close pairs of edges are avoided) would be to replace groups of single-to-single connections, all with the same source or sink and all with the same label, by a single-to-many or many-to-single confluent connection with only one label. The label clutter is as big or bigger an issue in these drawings than the edge clutter, and confluence can help with that.

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.