Correctly Modeling the Diagonal Capacity in Escape Routing

Research output: Contribution to journalJournal articlepeer-review

20 Citations (Scopus)


Escape routing for packages and printed circuit boards (PCBs) has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.
Original languageEnglish
Article number6132657
Pages (from-to)285-293
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number2
Publication statusPublished - 19 Jan 2012

User-Defined Keywords

  • Routing
  • Wires
  • Printed circuits
  • Network management
  • Diagonal capacity
  • escape routing
  • missing pin
  • network flow
  • package routing
  • printed circuit board (PCB) routing
  • 45° routing


Dive into the research topics of 'Correctly Modeling the Diagonal Capacity in Escape Routing'. Together they form a unique fingerprint.

Cite this