Space Efficient Algorithms for VLSI Artwork Analysis

We present algorithms for performing connectivity analysis, transistor identification, and boolean geometric operations with region numbering. Previous methods all require O(n) space where n is the number of edges in the circuit artwork; our method takes only O(√n) space and can therefore handle circuits of any foreseeable size. Our algorithms are based on traditional scanline techniques in such a way that any implementation of our method will be at least as fast, as well as more compact. Statistics on one such implementation are presented.