A Proper Model for Testing the Planarity of Electrical Circuits

Electrical networks frequently consist of a set of modules (beamleaded chips, DIPs, etc.), and a set of electrical interconnections or "nets" among two or more modules. Each net specifies a set of modules to be interconnected with a single conducting path. The planar design problem consists of placing the modules and the net wiring in the plane. The question of whether the interconnections can be accomplished in the plane without resorting to crossovers or multilayer wiring is usually answered by testing the planarity of a graph representing the circuit. This graph is typically constructed by one of two mappings: (i) Module-to-Xode Mapping. The modules are represented by the nodes (or points) of the graph; and the nets are represented by its edges (or lines); or (it) Module-to-Edge Mapping. The modules are represented by the edges and the nets are represented by the nodes. Since the edge of a graph connects exactly two nodes, these mappings are not uniquely defined and a priori design decisions must be made which may be either improper or restrictive, and may produce spurious crossovers (see Sections II and III). 135