1968/01/01 by Tony Nicholson · 3 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #VLSI and Analog Circuit Testing #Low-power high-performance VLSI design #Node (physics) #Permutation (music) #Random permutation #Computer science #Position (finance) #Line (geometry) #Monte Carlo method #Algorithm #Network planning and design #Network analysis #Theoretical computer science #Mathematics #Computer network #Combinatorics #Engineering #Geometry #Statistics
paper · doi:10.1049/piee.1968.0004
openalex publication_date 1968/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/26
The paper describes a method for laying out networks by computer so that the number of crossings between the network connections is close to a minimum. The problem is relevant to the design of printed circuits, where special wiring arrangements have to be made when crossings occur. The network is expressed in the form of a permutation, which is convenient for manipulation, by deforming the network so that the node points lie on a straight line with the connections drawn as semicircles above an below the node line. Locally optimal networks are defined so that no gain can result from moving an individual node to a new position, and a 2-stage method of construction is proposed. The formulas used to calculate the number of crossings consist primarily of summations, so that the procedure is quickly performed on a computer. The method has been tested on some trial networks for which the minimum number of crossings is known, and it has also been compared with Monte Carlo methods on random networks. The results are encouraging in all cases.