Slicing and non-slicing, unified and rotation independent, algebraic representation of floorplans

A floorplan is a rectangle envelope subdivided by horizontal and vertical line segments into n nonoverlapping basic rectangles, having given dimensions and relative positioning (i.e. topology). This paper presents a formal algebraic specification (in SETS notation) that is appropriate for VLSI physical design layout and capable of representing both the floorplan topology and the modules' dimensions. The specification proposed allows a concise and rigorous representation of arbitrarily complex composite floorplans. This algebraic description unifies-under a rotation-invariant single-expression formalism-slicing and non-slicing generalized wheels floorplans. As needed by specific floorplan algorithms, it supports either a topology-dimensionless description or the introduction of module dimensions. Finally, it allows an eightfold reduction-over previous representations-of the total number of floorplan solutions considered in floorplanning problem algorithms.