@inproceedings{1101628e5b5c4139b6cd62d044589bd0,
title = "A correct network flow model for escape routing",
abstract = "Escape routing for packages and 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 = "Diagonal capacity, Escape routing, Missing pin, Network flow, PCB routing, Package routing",
author = "Yan Tan and Wong, {Martin D.F.}",
year = "2009",
language = "English (US)",
isbn = "9781605584973",
series = "Proceedings - Design Automation Conference",
pages = "332--335",
booktitle = "2009 46th ACM/IEEE Design Automation Conference, DAC 2009",
note = "2009 46th ACM/IEEE Design Automation Conference, DAC 2009 ; Conference date: 26-07-2009 Through 31-07-2009",
}