1980/10/01 by Charles E. Leiserson · 5 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Low-power high-performance VLSI design #Very-large-scale integration #Graph #Computer science #Floorplan #Graph Layout #Planar graph #Time complexity #Graph drawing #Combinatorics #Mathematics #Theoretical computer science #Algorithm
paper · doi:10.1109/sfcs.1980.13
openalex publication_date 1980/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Minimizing the area of a circuit is an important problem in the domain of Very Large Scale Integration. We use a theoretical VLSI model to reduce this problem to one of laying out a graph, where the transistors and wires of the circuit are identified with the vertices and edges of the graph. We give an algorithm that produces VLSI layouts for classes of graphs that have good separator theorems. We show in particular that any planar graph of n vertices has an O(n lg2 n) area layout and that any tree of n vertices can be laid out in linear area. The algorithm maintains a sparse representation for layouts that is based on the well-known UNION-FIND data structure, and as a result, the running time devoted to bookkeeping is nearly linear.