Single row routing with bounded number of doglegs per net

Jitender S. Deogun, Arnob Roy, Naveed A. Sherwani

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


Sufficient and necessary conditions are presented for single-row routing when the number of doglegs per net is bounded by K, K = 1, 2. Algorithms for finding such realizations are developed. The necessary and sufficient conditions are based on a graph theoretic representation, in which an instance of the single-row routing problem is represented by three graphs: an overlap graph, a containment graph, and an interval graph.

Original languageEnglish (US)
Pages (from-to)43-46
Number of pages4
JournalProceedings - IEEE International Symposium on Circuits and Systems
StatePublished - 1989
EventIEEE International Symposium on Circuits and Systems 1989, the 22nd ISCAS. Part 1 - Portland, OR, USA
Duration: May 8 1989May 11 1989

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this