Theories and algorithms on single-detour routing for untangling twisted bus

Research output: Contribution to journalJournal articlepeer-review

4 Citations (Scopus)


Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call single-detour routing, to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Original languageEnglish
Article number46
Number of pages21
JournalACM Transactions on Design Automation of Electronic Systems
Issue number3
Publication statusPublished - May 2009

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Bus routing
  • Dynamic programming
  • Printed circuit board (PCB)
  • Single-detour routing
  • Twisted bus


Dive into the research topics of 'Theories and algorithms on single-detour routing for untangling twisted bus'. Together they form a unique fingerprint.

Cite this