Correctly Modeling the Diagonal Capacity in Escape Routing

Tan Yan; Martin D. F. Wong

doi:10.1109/TCAD.2011.2169258

Correctly Modeling the Diagonal Capacity in Escape Routing

Tan Yan, Martin D. F. Wong

Office of the Provost

Research output: Contribution to journal › Journal article › peer-review

22 Citations (Scopus)

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.

Original language	English
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	https://doi.org/10.1109/TCAD.2011.2169258
Publication status	Published - 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

Access to Document

10.1109/TCAD.2011.2169258

Cite this

@article{1c112264edbd4734bbfc44ca09abb4b8,

title = "Correctly Modeling the Diagonal Capacity in Escape Routing",

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.",

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

author = "Tan Yan and Wong, {Martin D. F.}",

note = "Funding Information: This work was supported in part by the National Science Foundation, under Grant CCF-1017516, and by a grant from the Fujitsu Laboratories. Publisher copyright: {\textcopyright} 2012, IEEE ",

year = "2012",

month = jan,

day = "19",

doi = "10.1109/TCAD.2011.2169258",

language = "English",

volume = "31",

pages = "285--293",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "IEEE",

number = "2",

}

TY - JOUR

T1 - Correctly Modeling the Diagonal Capacity in Escape Routing

AU - Yan, Tan

AU - Wong, Martin D. F.

PY - 2012/1/19

Y1 - 2012/1/19

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

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

KW - Routing

KW - Wires

KW - Printed circuits

KW - Network management

KW - Diagonal capacity

KW - escape routing

KW - missing pin

KW - network flow

KW - package routing

KW - printed circuit board (PCB) routing

KW - 45° routing

U2 - 10.1109/TCAD.2011.2169258

DO - 10.1109/TCAD.2011.2169258

M3 - Journal article

SN - 0278-0070

VL - 31

SP - 285

EP - 293

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 2

M1 - 6132657

ER -

Correctly Modeling the Diagonal Capacity in Escape Routing

Abstract

User-Defined Keywords

Access to Document

Fingerprint

Cite this