The list of Graph Drawing 2008 accepted papers is out.

Unlike some larger theory conferences, Graph Drawing allows program committee members to submit papers (but not to see or contribute to the deliberations on their own submissions) because otherwise it would be difficult to field a program committee without cutting off a large fraction of the conference's contributors. Therefore, although I was on the PC, I also have some papers in the list: two on xyz graphs and greedy embedding that I've already discussed here, and one additional short paper, “Isometric Diamond Subgraphs.” I don't want to spend a lot more space describing this last one, but let me just show a couple pretty pictures.

If you take the subset of the three-dimensional integer grid consisting of points whose coordinates sum to zero or one, it turns out to form a graph isomorphic to the regular hexagonal tiling of the plane (and can be mapped onto that tiling by an appropriate projection from 3d to 2d):

Hexagonal tiling labeled by coordinate triples that sum to zero or one

The same thing works to map a subset of a 4d grid to 3d, forming the structure of a diamond crystal:

Interior view of a diamond crystal

The paper describes how to use methods related to lattice dimension of partial cubes to test whether a given finite graph can be embedded in a distance-preserving way into these two infinite graphs and their higher dimensional generalizations.

There's plenty of other interesting research to be presented at the conference, so come to Crete and find out all about it!