Routing through a Rectangle

Mehlhorn, Kurt; Preparata, F. P.

doi:10.1145/4904.4994

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Routing through a Rectangle

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Preparata, F. P.
Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Mehlhorn, K., & Preparata, F. P. (1986). Routing through a Rectangle. Journal of the ACM, 33(1), 60-85. doi:10.1145/4904.4994.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AEC5-A

Abstract

In this paper an O(N log N) algorithm for routing through a rectangle is
presented. Consider an n-by-m rectangular grid and a set of N two-terminal
nets. A net is a pair of points on the boundary of the rectangle. A layout is a
set of edge-disjoint paths, one for each net. Our algorithm constructs a
layout, if there is one, in O(N log N) time; this contrasts favorably with the
area of the layout that might be as large as N2. The layout constructed can be
wired using four layers of interconnect with only O(N) contact cuts. A partial
extension to multiterminal nets is also discussed.