A polynomial time algorithm for optimal routing around a rectangle
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 282-293
- https://doi.org/10.1109/sfcs.1980.7
Abstract
In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component. Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t3), where t is the number of terminals on the component.Keywords
This publication has 8 references indexed in Scilit:
- The Complexity of Coloring Circular Arcs and ChordsSIAM Journal on Algebraic Discrete Methods, 1980
- LTX - a system for the directed automatic design of LSI circuitsPublished by Association for Computing Machinery (ACM) ,1976
- The interconnection problem: A tutorialComputer, 1974
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972
- Wire routing by optimizing channel assignment within large aperturesPublished by Association for Computing Machinery (ACM) ,1971
- Cellular wiring and the cellular modeling techniquePublished by Association for Computing Machinery (ACM) ,1969
- A solution to line-routing problems on the continuous planePublished by Association for Computing Machinery (ACM) ,1969
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961