On the Crossing Number of Tori

Reducing the number of link crossings in a network to a minimum is a difficult problem which has nonetheless important applications. Circuit design with very-large-scale integration (VLSI) is an example of such an application. This problem is known as the crossing number problem. Finding a general solution to this problem has been shown to be NP-hard. Hence, solutions for particular classes of graphs have been proposed. In this paper, we focus on tori as they have proven very popular as interconnection network of massively parallel systems; see for instance the Fujitsu K and Cray Titan supercomputers. We start by devising an optimal upper bound on the crossing number of a twodimensional k-ary torus. This first result is extended to obtain an upper bound on the crossing number of a three-dimensional k-ary torus. Finally, we derive from these discussions an upper bound on the crossing number of a k-ary n-dimensional torus. The proposed bounds and drawing methods are empirically evaluated with experiments involving system-generated torus drawings and the automatic calculation of their crossing numbers.