Via Minimization in VLSI Routing with Movable Terminals

Jitender S. Deogun, Bhargab B. Bhattacharya

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In this paper we develop a unified approach for solving the general problem of minimizing the number of “via holes” in a two-layer VLSI channel and switchbox routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switchbox routing, and (iii) four-sided switchbox routing. To solve the via minimization problem, we introduce the concept of a maximum parallel set of edges in a bipartite graph. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is 0(N log N), in all three cases, where N is the number of pairs of terminals to be connected.

Original languageEnglish (US)
Pages (from-to)917-920
Number of pages4
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number8
StatePublished - Aug 1989


  • Design automation
  • VLSI channel and switchbox routing
  • permutation graphs
  • via-minimization

ASJC Scopus subject areas

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


Dive into the research topics of 'Via Minimization in VLSI Routing with Movable Terminals'. Together they form a unique fingerprint.

Cite this