Abstract
A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. They are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.
| Original language | English |
|---|---|
| Title of host publication | Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009) |
| Place of Publication | New York NY |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 267-276 |
| ISBN (Print) | 978-1-60558-501-7 |
| DOIs | |
| Publication status | Published - 2009 |