On minimizing the number of L-shaped channels

Yang Cai, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

2 Citations (Scopus)


The problem of minimizing the number of L-shaped channels in the routing region definition and ordering for building-block layouts is studied. Given a building-block layout of rectangular modules, the routing region is to be decomposed into straight and L-shaped channels and routed in a certain order. Since channel routers usually produce superior results, it is desirable to minimize the number of L-shaped channels used in such a decomposition. A fast algorithm that can produce provably better results than a previously proposed algorithm is presented. This algorithm is based on a study of the structure of such layouts, and a transformation of the original problem to a graph theoretical problem. For examples of up to 136 channels, the algorithm took less than one-tenth of a second to finish the computation, and it obtained up to 29% reduction in the number of L-shaped channels over the results produced by another algorithm.

Original languageEnglish
Title of host publication28th ACM/IEEE Design Automation Conference - Proceedings 1991
PublisherAssociation for Computing Machinery (ACM)
Number of pages7
ISBN (Electronic)0818661496
ISBN (Print)0818691492, 9780818691492, 9780897913959, 0897913957
Publication statusPublished - Jun 1991
Event28th ACM/IEEE Design Automation Conference, DAC 1991 - San Francisco, United States
Duration: 17 Jun 199121 Jun 1991

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0146-7123


Conference28th ACM/IEEE Design Automation Conference, DAC 1991
Country/TerritoryUnited States
CitySan Francisco
Internet address

Scopus Subject Areas

  • Engineering(all)


Dive into the research topics of 'On minimizing the number of L-shaped channels'. Together they form a unique fingerprint.

Cite this