An Algorithm for Finding a Rectangular Dual of a Planar Graph for Use in Area Planning for VLSI Integrated Circuits

1 January 1984

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 0738100X,p. 655-656
https://doi.org/10.1109/dac.1984.1585872

Abstract

An O(n /sup 2/) algorithm for finding a rectangular dual of a planar triangulated graph is presented. In practice, almost linear running times have been observed. The algorithm is useful for solving area planning problems in VLSI IC design.

Keywords

VERY LARGE SCALE INTEGRATION
INTEGRATED CIRCUIT INTERCONNECTIONS
INTEGRATED CIRCUIT LAYOUT
CLUSTERING ALGORITHMS
ALGORITHM DESIGN AND ANALYSIS
POLYNOMIALS
SUFFICIENT CONDITIONS

Cited by 45 articles