Browsing by Author "Liang-Ping KU"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Optimum Partitioning of a Rectilinear Layout
    (1995-02-01T00:00:00Z) Liang-Ping KU; Hon Wai LEONG
    Given a rectilinear layout consisting of $n$ non-overlapping rectangles, we consider the problem of decomposing the remaining {\em free space} into rectangular {\em free blocks}. This problem is studied in connection with two problems from VLSI design, namely, design rule checking (DRC) using the corner stitching data structure, and the channel creation phase of global routing of VLSI building block layouts. In DRC using corner stitching, the decomposition is done via vertical partitioning. Similarly, horizontal partitioning can also be used. However, if we allow a hybrid of vertical and horizontal partitioning, the number of free blocks can be further reduced. In this paper, we consider the {\em optimum partitioning problem} in which we are interested in finding a decomposition that has the {\em minimum} number of free blocks. Given {\em any partition} of the free space, we first give a formula for counting the number of free blocks. The formula shows that the number of free blocks is determined by the number of {\em special} partition edges. We model the problem of finding an optimum partition as the problem of finding a maximum independent set in a bipartite graph. Finally, we give an $O( n ^ {2.5} ) $ algorithm for computing an optimum partition of any layout.