Correctly model the diagonal capacity in escape routing

Research output: Contribution to journalArticle

Abstract

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. 45

Original languageEnglish (US)
Article number6132657
Pages (from-to)285-293
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume31
Issue number2
DOIs
StatePublished - Feb 1 2012

Keywords

  • 45° routing
  • Diagonal capacity
  • escape routing
  • missing pin
  • network flow
  • package routing
  • printed circuit board (PCB) routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Correctly model the diagonal capacity in escape routing'. Together they form a unique fingerprint.

  • Cite this