Accession Number : AD0737151

Title :   On the Automated Layout of Multi-Layer Planar Wiring and a Related Graph Coloring Problem,

Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Abel,Luther Charles

Report Date : JAN 1972

Pagination or Media Count : 159

Abstract : Techniques for the automated layout or routing of computer hardware interconnections on a multi-layer planar wiring medium, particularly the assignment of connections to layers and the ordering or sequencing of connections for input to a maze-running type router, are investigated. Pairwise relationships between the rectilinear measure minimum distance rectangles for connections are used to create a pair of graphs -- an edge-weighted, undirected interference graph and a directed precedence graph. New methods for layer separation and connection sequencing based on analysis of these graphs using graph-theoretic techniques are proposed. (Author)

Descriptors :   (*LOGIC CIRCUITS, CIRCUIT INTERCONNECTIONS), (*SWITCHING CIRCUITS, GRAPHICS), WIRING DIAGRAMS, INTEGRATED CIRCUITS, GATES(CIRCUITS), MATHEMATICAL MODELS, LINEAR PROGRAMMING, THEOREMS, THESES, AUTOMATION, COLORS

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE