Suresh has been blogging up a storm about SoCG, while instead I played hooky this afternoon to visit Seokguram and Bulguksa. (Sadly, the light was grey and flat, so don't expect photos, but both were definitely worth seeing in person.) Except for the difficulty of getting here, this has been a great location for a conference: a high quality hotel with reasonable rates, nearby restaurants with great food at low prices (my favorite so far: Bersayu, an excellent sit-on-the-floor barbecue dinner for about $6), decent espresso nearby albeit at high prices, and an impressive cultural heritage.

Anyway, here at least are the talk slides from my two talks yesterday: Guard placement for wireless localization (with Nodari Sitchinava and Mike Goodrich) and Happy endings for flip graphs.

Happy Endings for Flip Graphs was accepted to SoCG 2007, as was another paper of mine: Guard Placement For Wireless Localization, with Mike Goodrich and Mike's student Nodari Sitchinava. So I guess that means I'm going to Korea...

ETA: The full acceptance list, Suresh's minimalist remarks, and Sariel's hideous frozen cat atrocity.

I've written up my results on flip graphs, partial cubes, and the happy ending theorem, and uploaded it to arxiv: Happy endings for flip graphs.

The triangulations of a regular n-gon, embedded in the plane with a marked edge, can be placed in one-to-one correspondence with binary trees having n-1 leaves: each tree is essentially just the planar dual graph to a triangulation, rooted at the marked edge. But the markings needed for this correspondence mess up the symmetry of the n-gon.

This issue of symmetry has some relevance to geometric constructions of the associahedron, the polytope whose skeleton is the flip graph of triangulations or the rotation graph of binary trees. One would like a realization of the associahedron as a geometric object with at least as much symmetry as the regular polygon being triangulated, but the general constructions I've seen for embedding associahedra as polytopes don't do that, and I don't know whether it's possible in general. I can see how to do it in two and three dimensions, but after that my ability to visualize what's happening runs into trouble...

( Read more... )

This is the flip graph of a convex hexagon. It is planar, but I wanted to communicate (1) that it is the skeleton of a polyhedron (the associahedron), and (2) that the top and bottom vertices are at distance four from each other. I think the drawing below communicates that better than a planar drawing would have. It's a bit distorted from the projection of a symmetric convex polyhedron, I think, mainly because I wanted to avoid having the middle row of triangulations overlap each other.

Someone asked me where I was going with flip graphs of grids, and I didn't know at the time. But I got a hint the other night, and now I think I can prove it: a point set has a partial cube flip graph if and only if it has no empty pentagon. I think I'll wait until writing it up more carefully to give details of the proof, but the significance of this (beyond being pretty) is that it means we can compute the flip distances for these point sets easily, compared to e.g. convex polygons where computation of flip distances is a famous open problem (see e.g. Sleator Thurston and Tarjan 1986). Also I think the proof is easier in this level of generality than it is for grids.

To keep this from being content-free, here's an example showing that point sets without empty pentagons can be complicated. One more level of inscribed pentagons and there would be an empty one... I also have several infinite families beyond the one we already knew, convex subsets of a projective transformation of a grid.

I know it's ridiculously late, but when I get ideas late at night I tend not to be able to sleep until I write them down, and here's as good a place as any for that.

Anyway, you remember (or probably you don't, but I do) that classification of dilation-free planar graphs I did a while back, that's now been incorporated into a paper with Dujmović, Suderman, and Wood?

( Read more... )

So anyway, there's a much easier way to describe the same family of point sets, closely related to the famous happy ending problem: these are exactly the point sets that have no strictly-convex empty quadrilateral. They're also the point sets with exactly one triangulation.

( Proof sketch )

It's known by now that every sufficiently large point set in general position has a strictly-convex empty hexagon but of course these point sets aren't in general position...

The labeling scheme I described for the 3x3 grid appears to generalize to show that any grid has a flip graph that embeds isometrically into a hypercube.

( Cut for somewhat technical sequence of lemmas and proofs with no figures )

Here is the flip graph of 3x3 triangulations again, with the triangulations grouped according to their set of length-sqrt(2) edges. The number of edges shown between each pair of groups indicates the number of pairs of triangulations that can be flipped from one group to the other. Despite not showing the detailed connections as well, I think this kind of clustered graph drawing makes the overall structure of the flip graph much clearer.

( Cut for large image )

Following up my recent post on triangulations of points on two lines, I spent some time on the plane home today thinking about the next simplest case: a 3x3 grid. It turns out that the triangulations of these 9 points can be labeled by 12-dimensional bitvectors in such a way as to make them a partial cube.

( Read more... )

This still seems a small enough example that I'm not willing to guess whether the partial cube property generalizes to larger grids.

I'm in Karlsruhe for Graph Drawing 2006. The first day had many interesting talks; my own (in the session on tree drawing) seemed to go well, and I've put the slides online here.

( Non-crossing configurations and partial cube flip graphs )