ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

On the Crossing Number of Tori

Proceeding: The Fourth International Conference on Electronics and Software Science (ICESS2018)

Publication Date:

Authors : ; ; ;

Page : 55-64

Keywords : VLSI; Interconnect; Network; Intersection; Circuit;

Source : Downloadexternal Find it from : Google Scholarexternal


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.

Last modified: 2019-01-20 20:49:14