**Orientation-constrained rectangular layouts**.

D. Eppstein and E. Mumford.

arXiv:0904.4312.

Algorithms and Data Structures Symposium (WADS), Banff, Canada.

Springer,*Lecture Notes in Comp. Sci.*5664, 2009, pp. 266–277.We show how to find a stylized map in which regions have been replaced by rectangles, preserving adjacencies between regions, with constraints on the orientations of adjacencies between regions. For an arbitrary dual graph representing a set of adjacencies, and an arbitrary set of orientation constraints, we can determine whether there exists a rectangular map satisfying those constraints in polynomial time. The algorithm is based on a representation of the set of all layouts for a given dual graph as a distributive lattice, and on Birkhoff's representation theorem for distributive lattices.

Merged with "Area-universal rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".

(Slides)

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.