Area-Universal Rectangular Layouts
| dc.creator | Eppstein, David | |
| dc.creator | Mumford, Elena | |
| dc.creator | Speckmann, Bettina | |
| dc.creator | Verbeek, Kevin | |
| dc.date | 2009-01-25 | |
| dc.date.accessioned | 2026-07-07T12:34:28Z | |
| dc.date.available | 2026-07-07T12:34:28Z | |
| dc.description | A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. Rectangular layouts appear in various applications: 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 might hence be desirable if one rectangular layout can 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. More generally, given any rectangular layout L and any assignment of areas to its regions, we show that there can be at most one layout (up to horizontal and vertical scaling) which is combinatorially equivalent to L and achieves a given area assignment. 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. | |
| dc.description | 19 pages, 16 figures | |
| dc.identifier | https://arxiv.org/abs/0901.3924 | |
| dc.identifier | http://arxiv.org/abs/0901.3924 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/217446 | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.2 | |
| dc.title | Area-Universal Rectangular Layouts | |
| dc.type | text |