### 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(t^{3}), where t is the number of terminals on the component.

Original language | English (US) |
---|---|

Article number | 4567829 |

Pages (from-to) | 282-293 |

Number of pages | 12 |

Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |

DOIs | |

State | Published - Jan 1 1980 |

Event | 21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States Duration: Oct 13 1980 → Oct 15 1980 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Fingerprint Dive into the research topics of 'A polynomial time algorithm for optimal routing around a rectangle'. Together they form a unique fingerprint.

## Cite this

*Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS*, 282-293. [4567829]. https://doi.org/10.1109/SFCS.1980.4567829