09/01/1992 09:00 AM
Computer Engineering
The flexible rubber-band sketch is a useful representation for routing interconnect. In addition to supporting an incremental design style, rubber-bands provide a flexible framework for generating layout under performance constraints. However, due to reasons of compatibility between CAD tools, it may be necessary at times to convert a rubber-band sketch to a more restricted geometry such as rectilinear or octilinear wiring. This paper presents an efficient method, based on the enhanced plane sweep, for converting a rubber- band sketch to a topologically equivalent rectilinear or octilinear wiring with minimum wire length. A sketch with n rubber-band segments can be converted to a restricted geometry with m segments in O(n \\log n + m) time. In addition to guaranteeing minimum wire length, the technique uses heuristic methods to reduce the total number of jogs. Notes: M.S. Thesis
