Abstract

Single-row routing is a technique for routing pair of nodes arranged in a single-row axis or set of nets. The nets make up the wire without crossing each other in the printed circuit board design which is drawn from left to right. The main objective in single-row routing is to achieve the optimal results of minimum congestion arising from the number of horizontal tracks in the network. Optimal results for a single layer network have been achieved through a model called enhanced simulated annealing for single-row routing (ESSR). However, a single layer model suffers from non-tolerable lower bound values with high congestion depending on the network size. These results may further be improved by partitioning the network into two or more layers. In this paper, a technique based on the graph clustering concept for partitioning the nodes from a single-row network into several layers of planar graphs by using k-means algorithm has been proposed. The experiment result shows that the proposed technique is able to minimize the network congestions.

Key words: Enhanced simulated annealing for single-row routing (ESSR), graph clustering, k-means algorithm, single-row routing.