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

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)

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1972
Accession Number
AD0737151

Entities

People

  • Luther Charles Abel

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Computers
  • Computing Devices
  • Contracts

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.