Corner-Stitching-Based Multilayer Obstacle-Avoiding Component-to-Component Rectilinear Minimum Spanning Tree Construction

Yen Yu Su, Shuo Hui Wang, Wei Liang Wu, Mark Po Hung Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Engineering change orders (ECOs) are pervasively applied to modern physical design of nanometer integrated circuits for cost-effective design changes. After applying ECO, a net may become open, which results in a large number of disconnected net components. Each net component further consists of a set of connected net shapes and vias on different layers. It is very challenging to efficiently and effectively identify all disconnected net components and find an obstacle-avoiding minimal-cost routing path among those net components. This paper introduces an open-net finder and an open-net connector based on the corner-stitching data structure for open-net routing, and proposes a new method of constructing a multilayer obstacle-avoiding component-to-component rectilinear minimum spanning tree. The preliminary idea and implementation of the proposed method had received the first place award in ICCAD-2017 CAD contest. This paper further details the complete idea of the proposed method. Experimental results show that the proposed open-net finder and connector outperform the top three open-net routers in the ICCAD-2017 CAD contest and two latest published works, with better routing costs and much shorter runtime.

Original languageEnglish
Article number8599013
Pages (from-to)675-685
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
StatePublished - Mar 2020


  • Corner stitching
  • engineering change order (ECO)
  • minimal spanning tree
  • minimum spanning tree (MST)
  • multilayer
  • obstacle
  • physical design
  • rectilinear
  • routing


Dive into the research topics of 'Corner-Stitching-Based Multilayer Obstacle-Avoiding Component-to-Component Rectilinear Minimum Spanning Tree Construction'. Together they form a unique fingerprint.

Cite this