TCG: A transitive closure graph-based representation for general floorplans

Jai Ming Lin, Yao Wen Chang

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)


In this brief, we introduce the concept of the P*-admissible representation and propose a P*-admissible, transitive closure graph-based representation for general floorplans, called transitive closure graph (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 a 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 of 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)288-292
Number of pages5
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number2
Publication statusPublished - 2005 Feb

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

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

Cite this