I've uploaded another WADS paper to the arxiv today: Orientation-Constrained Rectangular Layouts (with Elena Mumford, arXiv:0904.4312). It's a follow-up to our paper to appear at SoCG on rectangular cartograms, stylized maps in which countries or other regions are replaced by rectangles whose areas represent numerical quantities associated with the regions. In the SoCG paper, we were concerned about area-universality, the ability to morph a cartogram from any set of areas to any other set without changing the orientations of the rectangles, but here we're concerned about a more basic question: which sets of orientations are possible? If, say, I wanted to draw a cartogram for the counties of southern California, it would help readers understand which rectangle corresponds to which county if they could be placed in something resembling their geographic arrangement. For instance, Los Angeles County should be placed above (to the north of) Orange County, or at least not directly below it where San Diego County should be.

We represent the problem by a dual graph in which each vertex represents a region of the desired cartogram and each edge represents an adjacency between regions. Two adjacent regions may be in any of four geometric relations to each other (above, below, left, or right, depending on the orientation of their shared boundary) and we allow constraints restricting them to any subset of these four relations. We also allow more complicated constraints restricting the orientations of triples of regions that meet at a T-junction; for instance, we can constrain one of the three regions to be the one that covers an angle of π at the junction, forcing the other two to have corners there. The question is, given a dual graph and a system of constraints of this type, can we find a cartogram that obeys all the constraints? As we show, this can be answered in polynomial time. It's also possible to combine the algorithms from this paper with the ones from the SoCG paper, and find an area-universal orientation-constrained layout (if it exists) in the same fixed-parameter-tractable time bounds as the ones from SoCG.

The proof idea is to take a step backwards from the problem, looking at it more abstractly, by considering the set of all layouts of the given dual graph as forming a distributive lattice (one that is too big to search or represent explicitly within an efficient algorithm), and then to take a step back again and use Birkhoff's representation theorem to view the lattice as generated from a (polynomially sized) partial order. The orientation constraints are transformed at this level of abstraction (with some technical details involving separating quadrilaterals of the dual graph) into an equivalence relation on the elements of the partial order, which can be used to generate a different partial order whose distributive lattice represents only the layouts that satisfy the constraints.

It makes me happy to be able to use our understanding of abstract cubical systems (of which distributive lattices are an example) to solve concrete problems like this, and the clean lattice-theoretic representation of this problem is also what makes the part about combining it with the SoCG algorithms work. But seeing a deep and highly abstract algorithm like this one makes me a little itchy: there's some inherent loss of efficiency in going from the dual graph to the partial order (the partial order has size quadratic in the input), and I can't help wondering whether there's some more direct method that might be more efficient and also possibly easier to explain and understand.