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

Fingerprint

Printed circuit boards

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

Cite this

Correctly model the diagonal capacity in escape routing. / Yan, Tan; Wong, Martin D F.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 31, No. 2, 6132657, 01.02.2012, p. 285-293.

Research output: Contribution to journalArticle

@article{45ff421d064e43f6b387705687569398,
title = "Correctly model 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. 45",
keywords = "45° routing, Diagonal capacity, escape routing, missing pin, network flow, package routing, printed circuit board (PCB) routing",
author = "Tan Yan and Wong, {Martin D F}",
year = "2012",
month = "2",
day = "1",
doi = "10.1109/TCAD.2011.2169258",
language = "English (US)",
volume = "31",
pages = "285--293",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - Correctly model the diagonal capacity in escape routing

AU - Yan, Tan

AU - Wong, Martin D F

PY - 2012/2/1

Y1 - 2012/2/1

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

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

KW - 45° routing

KW - Diagonal capacity

KW - escape routing

KW - missing pin

KW - network flow

KW - package routing

KW - printed circuit board (PCB) routing

UR - http://www.scopus.com/inward/record.url?scp=84856472623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856472623&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2011.2169258

DO - 10.1109/TCAD.2011.2169258

M3 - Article

AN - SCOPUS:84856472623

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

SN - 0278-0070

IS - 2

M1 - 6132657

ER -