I'm back from Graph Drawing 2010, which I enjoyed very much. I hope to have some longer posts addressing specific topics from the conference later, but in the meantime let me just point to this TCSexchange question in which Sariel Har-Peled proves that it's NP-complete to test whether a k-regular graph has a Lombardi drawing with all vertices on a common circle, in the case that k is 2 (mod 4) and greater than two.

Actually what Sariel proves is that for any k it is NP-complete to test whether k-regular graphs have Hamiltonian cycles, even in a more restricted case in which (for even values of k) you restrict the number of vertices in the graph to be odd. The connection from that combinatorial problem to the graph drawing problem is made in my paper on Lombardi drawing with Christian Duncan, Mike Goodrich, Stefan Kobourov, and Martin Nöllenburg. This hardness result makes a curious contrast to the cases of circular Lombardi drawing of k-regular graphs for odd k or k divisible by 4, which are both solvable in polynomial time.

Christian gave the talk on this paper at GD using prezi, presentation software that builds your presentation as one large image and then zooms around to different frames of interest selected from it. I like the idea that one can use a single mental map to assign locations in the big image to different concepts from the talk, and I think the novelty of this presentation style made for a memorable talk, but i did hear some complaints that all that zooming made the audience dizzy.




Comments:

leonardo_m:
2010-09-26T14:38:52Z
Christian gave the talk on this paper at GD using prezi, presentation software that builds your presentation as one large image and then zooms around to different frames of interest selected from it. I like the idea that one can use a single mental map to assign locations in the big image to different concepts from the talk, and I think the novelty of this presentation style made for a memorable talk, but i did hear some complaints that all that zooming made the audience dizzy.

It's a nice idea, that few years ago I have seen (with images too and in a more extreme version) done in Flash still, I don't remember its name, it was maybe Subtext. But I see it more fit for a personal exploration of a topic and less fit for a slide show. The people that look at the presentation have to follow a story, so there's no need to zoom a lot.

And even for a personal exploration, I am not sure it's a good idea. The idea of giving a hierarchical structure to a text is very good, but I think better ways to do it are needed.