I just uploaded another paper to arxiv, "Regular Labelings and Geometric Structures", arXiv:1007.0221. It's a survey about some unexpected similarities between lattice embeddings of planar graphs, partitions of rectangles into smaller rectangles, and orthogonal polyhedra. All of these things can be described combinatorially by a "regular labeling" consisting of a coloring and orientation of an associated maximal planar (or nearly maximal planar) graph. All of these regular labelings have local constraints at what the labeling can look like near a vertex, and in all of them these local constraints force certain subgraphs formed by edges of one or two colors to be acyclic. In all three cases there are simple characterizations of the graphs that support a labeling, that lead to efficient algorithms for constructing the objects described by the labeling. And in all three cases the possible labelings of a fixed graph form a distributive lattice in which adjacent labelings differ from each other by a local twist operation. I don't really understand why these things should act so similarly to each other and in part I wrote this as a request for a better explanation. But it's also a teaser for my invited talk at CCCG this summer, at which I plan to talk about this material in a little more detail.

On a related note, the slides from my coauthor Elena Mumford's talk on orthogonal polyhedra at SoCG last month are now online.