de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Routing through a Rectangle

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

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

Preparata,  F. P.
Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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, 60-85.


Cite as: http://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.