Layer assignment for multi-layer PCB and VLSI routing

Kuo En Chang*, Sung Chuan Fang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

Original languageEnglish
Pages (from-to)373-382
Number of pages10
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Issue number4
Publication statusPublished - 1991 Jun


  • Graph contractability
  • Layer assignment
  • NP-compIete
  • Via minimization

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Layer assignment for multi-layer PCB and VLSI routing'. Together they form a unique fingerprint.

Cite this