FLOORPLANS, PLANAR GRAPHS, AND LAYOUTS

The topics discussed are minimization of the area occupied by a layout and related results concerning networks flow and rectilinear representation of planar graphs, based on a graph model of floorplans and layouts. Arbitrary floorplans are allowed. Given an arbitrary floorplan and the areas of the embedded building blocks, the existence and uniqueness of a zero wasted area layout are proved, and characterized by a necessary and sufficient condition. Based on this condition, a scheme is described to generate zero-wasted-area layouts. Given a family of dual network pairs for which the product of dual arc lengths are invariant, it is proved that the minimal product of their longest paths is not smaller than the maximal product of their shortest paths. It is also shown that the maximal product of the flows in such a family of dual network pairs is given by the total sum of the arc length product of each individual pair of dual arcs. An efficient procedure to derive a rectilinear representation for any planar graph is presented.