BSG-route: A length-constrained routing scheme for general planar topology

Research output: Contribution to journalJournal articlepeer-review

19 Citations (Scopus)


Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-sliceline grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day.

Original languageEnglish
Pages (from-to)1679-1690
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
Early online date20 Oct 2009
Publication statusPublished - Nov 2009

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Algorithms
  • Linear programming (LP)
  • Printed circuit layout
  • Routing


Dive into the research topics of 'BSG-route: A length-constrained routing scheme for general planar topology'. Together they form a unique fingerprint.

Cite this