ABSTRACT
This chapter focuses on the early approaches to the floorplanning phase in the context of full-custom design or semicustom design styles such as building blocks, standard cells, and gate arrays. In physical design, floorplanning determines the topology of the layout, i.e., the relative positions of modules on the chip, based on the interconnection requirements of the circuit and estimates for area. A floorplan generated by rectangular dualization is often referred to as a rectangular dual. The fact that a rectangular graph can have more than one nonisomorphic dual brings us to the fundamental question about the existence of rectangular graphs that have no slicible duals. This is equivalent to characterizing slicibility of rectangular graphs. A rectangular graph is inherently nonslicible if there exists no slicible rectangular dual of it, consequently no slicible floorplan. As finding an optimal solution to the floorplanning problem is computationally expensive, hierarchical approach for handling larger instances is a natural choice.
