Area-universal rectangular layouts

D. Eppstein, E. Mumford, B. Speckmann, K.A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

17 Citations (Scopus)
1 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages267-276
ISBN (Print)978-1-60558-501-7
DOIs
Publication statusPublished - 2009

Cite this