Area-universal and constrained rectangular layouts

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

36 Citaten (Scopus)
111 Downloads (Pure)


A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. These layouts 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. Furthermore we show how to impose restrictions on the orientations of edges and junctions of the rectangular 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.
Originele taal-2Engels
Pagina's (van-tot)537-564
TijdschriftSIAM Journal on Computing
Nummer van het tijdschrift3
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Area-universal and constrained rectangular layouts'. Samen vormen ze een unieke vingerafdruk.

Citeer dit