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

Research output: Contribution to journalArticlepeer-review


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 (US)
Article number5290341
Pages (from-to)1679-1690
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
StatePublished - Nov 2009


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

ASJC Scopus subject areas

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


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