On the crossing numbers of loop networks and generalized Petersen graphs

Bhatt and Leighton proved that the crossing number of a network (graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the crossing numbers of graphs with good interconnection properties, such as the circulant graphs G(n;±s1,…,±sm). In this work we find tight bounds for the crossing numbers of the (double fixed step) circulant graphs G(n;±1,±k). Specifically, we show that for values of n sufficiently large compared to k, the crossing number of G(n;±1,±k) is bounded by above and by below by linear functions of n, both of which have coefficients that approach 1 as k goes to infinity. As an additional application of these bounds, we show that the crossing numbers of the generalized Petersen graphs P(n,k) are bounded by below and by above by linear functions of n, whose coefficients approach 25 and 2, respectively, as k goes to infinity.