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 language | English (US) |
|---|---|
| Article number | 6132657 |
| Pages (from-to) | 285-293 |
| Number of pages | 9 |
| Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
| Volume | 31 |
| Issue number | 2 |
| DOIs | |
| State | Published - Feb 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