Testing the Two-Layer Routability in a Circular Channel

Noriya KOBAYASHI  Masahiro ABE  Toshinobu KASHIWABARA  Sumio MASUDA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.1   pp.83-91
Publication Date: 1992/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Computer Aided Design (CAD)
Keyword: 
algorithm,  routing problem,  via minimization,  

Full Text: PDF(657.9KB)>>
Buy this Article



Summary: 
Suppose that there are terminals on two concentric circles Cin and Cout, with Cin inside of Cout. A set of two-terminal nets is given and the routing area is the annular region between the two circles. In this paper, we present an O(n2) time algorithm for testing whether the given net set is two-layer routable, where n is the number of nets. Applying this algorithm repeatedly, we can find, in O(n3) time, a maximal subset of nets which is two-layer routable.