A Topological Sorting Algorithm For Three-Layer Channel Routing

Kuo En Chang*, Tin Hung Lai, Wu Shiung Feng

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review


Three-layer channel routing is an important problem in VLSI layout. In this paper, we present a topological sorting algorithm to determine the topological order on nets depending on the operations of the vertical con-.straint graph (VCG) and the horizontal constraint graph (HCG). According to the order, the base router can finish the connections of all nets. In the algorithm, the HVH mode is assumed, and some examples including Deutsch’s difficult example are used as test problems.

Original languageEnglish
Pages (from-to)673-683
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 number6
StatePublished - 09 1990
Externally publishedYes


  • Channel routing
  • Topological sorting


Dive into the research topics of 'A Topological Sorting Algorithm For Three-Layer Channel Routing'. Together they form a unique fingerprint.

Cite this