AREA-UNIVERSAL AND CONSTRAINED RECTANGULAR LAYOUTS

作者：Eppstein David^*; Mumford Elena; Speckmann Bettina; Verbeek Kevin

来源：SIAM Journal on Computing, 2012, 41(3): 537-564.

DOI：10.1137/110834032

• computational geometry
• rectangular layout
• rectangular cartogram
• area-universal
• one-sided

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.

• 出版日期2012