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

摘要

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)