Floorplans, Planar Graphs, and Layouts

Abstract

The topics discussed in this paper 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. We do not restrict our analysis to sliced floorplans but allow arbitrary floorplans. Given an arbitrary floorplan and the areas of the embedded building blocks, we prove the existence and uniqueness of a zero wasted area layout, and characterize it by a necessary and sufficient condition. On the basis of this condition we develop a scheme to generate zero wasted area layouts. We prove that given a family of dual network pairs for which the product of dual arc lengths are invariant, the minimal product of their longest paths is not smaller than the maximal product of their shortest paths. We also show 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. Finally, based on the zero wasted area layout, we present an efficient procedure to derive a rectilinear representation for any planar graph. ©1988 IEEE