Area-Efficient Graph Layouts (for VLSI).

Abstract

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 lg-square(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 management of this representation is nearly linear. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 13, 1980
Accession Number
ADA096367

Entities

People

  • Charles E. Leiserson

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Aspect Ratio
  • Circuit Boards
  • Circuits
  • Computer Science
  • Computers
  • Construction
  • Efficiency
  • Integrated Circuits
  • Lists (Data Structures)
  • Networks
  • Printed Circuit Boards
  • Printed Circuits
  • Separators
  • Transistors
  • Trees (Data Structures)

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.