Space-efficient extraction algorithms
Nick P. van der Meijs, A.J. van Genderen · 2003
A description is given of how the authors limited the space complexity of a layout to circuit extractor by: a combination of the scanline technique with the corner stitching technique; a region-based extraction algorithm; a judicious choice of netlist format; and a union-find data structure also supporting deletions of elements. The efficiency of the new algorithms and the resulting extractor is confirmed by experimental data. These results are important, since in practice the size of the largest design that can be handled is often hard-limited by available memory.>