SLICEABLE FLOORPLANNING BY GRAPH DUALIZATION

Previous algorithms on rectangular dual graph floorplanning generate g eneral floorplans which include the class of nonsliceable floorplans. We examine the framework of generating sliceable floorplans using the rectangular dual graph approach and present an algorithm that generate s a sliceable floorplan if the input graph satisfies certain sufficien t conditions. For general input, the algorithm is still able to genera te sliceable floorplans by introducing pseudomodules where the areas o ccupied by the pseudomodules are used for wiring. For an n-vertex adja cency graph, the algorithm generates a sliceable floorplan in O(n log n + hn) time where h is the height of the sliceable floorplan tree.