We construct partitions of rectangles into smaller rectangles from an input consisting of a planar dual graph of the layout together with restrictions on the orientations of edges and junctions of the layout. Such an orientation-constrained layout, if it exists, may be constructed in polynomial time, and all orientation-constrained layouts may be listed in polynomial time per layout.
|Title of host publication||Algorithms and Data Structures (Proceedings 11th International Workshop, WADS 2009, Banff, Alberta, Canada, August 21-23, 2009)|
|Editors||F. Dehne, M. Gavrilova, J.-R. Sack, C.D. Tóth|
|Place of Publication||Berlin|
|Publication status||Published - 2009|
|Name||Lecture Notes in Computer Science|