TCG: A transitive closure graph-based representation for non-slicing floorplans

J. M. Lin, Y. W. Chang

Research output: Contribution to journalConference articlepeer-review

211 Citations (Scopus)


In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

Original languageEnglish
Pages (from-to)764-769
Number of pages6
JournalProceedings - Design Automation Conference
Publication statusPublished - 2001 Jan 1
Event38th Design Automation Conference - Las Vegas, NV, United States
Duration: 2001 Jun 182001 Jun 22

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering


Dive into the research topics of 'TCG: A transitive closure graph-based representation for non-slicing floorplans'. Together they form a unique fingerprint.

Cite this