A graph-theoretical approach to a problem in circuit design. (English) Zbl 0608.94014
Mitt. Math. Semin. Gießen 175, 19-26 (1986).
The via-minimisation problem for a two-layered PC-board is shown to be NP-complete if arbitrary intersection points of line segments may be cruxes, i.e. must not become a via. This result is derived by associating a graph \(G_ T\) with the layout T of the circuit to be printed on the board. The via-minimisation problem is equivalent to the maximum-cut problem with respect to \(G_ T\) which is NP-complete if no restrictions are known for the graph. The author gets his result by showing that any graph may be associated with a PC-board, if cruxes are allowed.
Reviewer: H.Schmeck
MSC:
94C15 | Applications of graph theory to circuits and networks |
68Q25 | Analysis of algorithms and problem complexity |
68R10 | Graph theory (including graph drawing) in computer science |