Graph contractability problem for vlsi layer assignment

Kuo En Chang*, Horng Fei Jyu, Wu Shuing Feng

*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 transform the problem of layer assignment for three-layer routing to the contractability problem of 3-colorable graph. This problem is shown to be NP-complete and a heuristic algorithm is proposed on the basis of the graph contractability model. From our experimental results, the algorithm is faster and efficient to generate very good results. In the average, the number of vias can be reduced by 30 percent or so.

Original languageEnglish
Pages (from-to)485-495
Number of pages11
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 - 1989 Jun


  • Crossing graph
  • Graph contractability
  • Layer assisgnment
  • NP-complete

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Graph contractability problem for vlsi layer assignment'. Together they form a unique fingerprint.

Cite this