Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 43-46 |
Number of pages | 4 |
Journal | Proceedings - IEEE International Symposium on Circuits and Systems |
Volume | 1 |
State | Published - 1989 |
Event | IEEE International Symposium on Circuits and Systems 1989, the 22nd ISCAS. Part 1 - Portland, OR, USA Duration: May 8 1989 → May 11 1989 |
ASJC Scopus subject areas
- Electrical and Electronic Engineering