Graph theoretic technique to speed up floorplan area optimization

Ting Chi Wang, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Number of pages7
ISBN (Print)0818628227
StatePublished - 1992
Externally publishedYes
EventProceedings of the 29th ACM/IEEE Design Automation Conference - Anaheim, CA, USA
Duration: Jun 8 1992Jun 12 1992

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123


OtherProceedings of the 29th ACM/IEEE Design Automation Conference
CityAnaheim, CA, USA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Graph theoretic technique to speed up floorplan area optimization'. Together they form a unique fingerprint.

Cite this