Efficient net extraction for restricted orientation designs

Mario A. Lopez, Ravi Janardan, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, i;, of different orientations of the line segments or polygons in a practical VLSI mask design is small relative to the number, n, of segments or polygon edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop and implement a practical algorithm for net extraction that runs in O(cnlogn) time and O(n) space, which is optimal for fixed c. The algorithm uses only integer operations and is, as a result, numerically stable. Experiments indicate that the algorithm will outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

Original languageEnglish (US)
Pages (from-to)1151-1159
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - 1996


Dive into the research topics of 'Efficient net extraction for restricted orientation designs'. Together they form a unique fingerprint.

Cite this