On the difficulty of Manhattan channel routing

TitleOn the difficulty of Manhattan channel routing
Publication TypeJournal Articles
Year of Publication1992
AuthorsGreenberg R, JaJa JF, Krishnamurthy S
JournalInformation Processing Letters
Pagination281 - 284
Date Published1992/12/21/
ISBN Number0020-0190
Keywordscombinatorial problems, computational complexity, lower bounds, VLSI channel routing

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Ω(n) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.