Area-universal rectangular layouts

DOI10.1145/1542362.1542411MaRDI QIDQ5370726zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David Eppstein, Elena Mumford, Bettina Speckmann, Kevin Verbeek

Publication date 20 October 2017

Published in Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.3924

zbMATH Keywords

rectangular layouts

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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.

Recommendations

• Area-universal and constrained rectangular layouts
• Aspect ratio universal rectangular layouts
• Orientation-Constrained Rectangular Layouts
• Generic rectangulations
• scientific article; zbMATH DE number 1300642

Cited in

(11)

• On area-universal quadrangulations
• Linear-time algorithm for generating L-shaped floorplans using canonical ordering technique
• Area-universal and constrained rectangular layouts
• A graph theoretic approach for generating T-shaped floor plans
• Exploiting air-pressure to map floorplans on point sets
• On mathematical optimization for the visualization of frequencies and adjacencies as rectangular maps
• Exploiting air-pressure to map floorplans on point sets
• Orientation-Constrained Rectangular Layouts
• Rectangular layouts and contact graphs
• Computing stable Demers cartograms
• A theory of L-shaped floor-plans

This page was built for publication: Area-universal rectangular layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370726)