A New Approach to Three- or Four-Layer Channel Routing

Jingsheng Cong, D. F. Wong, C. L. Liu

Research output: Contribution to journalJournal articlepeer-review

35 Citations (Scopus)


We present in this paper a new approach to the three- or four-layer channel routing problem. Since two-layer channel routing has been well studied, there are several two-layer routers which can produce optimal or near optimal solutions for almost all the practical problems. We develop a general technique which transforms a two-layer routing solution systematically into a three-layer routing solution. This solution transformation approach is different from previous approaches for three-layer and multilayer channel routing. Our router performs well in comparison with other three-layer channel routers proposed thus far. In particular, it provides a ten-track optimal solution for the famous Deutsch's difficult example, whereas other well known three-layer channel routers required 11 or more tracks. We extend our approach to four-layer channel routing. Given any two-layer channel routing solution without an unrestricted dogleg that uses w tracks, our router can provably obtain a four-layer routing solution using no more than ⌈w/2⌉ tracks. We also give a new theoretical upper bound ⌈d/2⌉+2 for arbitrary four-layer channel routing problems.

Original languageEnglish
Pages (from-to)1094-1104
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number10
Publication statusPublished - Oct 1988

Scopus Subject Areas

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


Dive into the research topics of 'A New Approach to Three- or Four-Layer Channel Routing'. Together they form a unique fingerprint.

Cite this