The crossing number of Knödel graph W3,n

Abstract

Knodel graphs have been widely studied as interconnection networks, mainly because of their good properties in terms of broadcasting and gossiping. 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. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete (Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4 (1983) 312-316). With this important application in mind, it makes most sense to analyze the crossing number of Knodel graphs. In this paper we study the crossing number of the Knodel graph W_3,n, and prove that cr(W_3,8) = 0, cr(W_3,10) = 1 and cr(W_3,n) = [n/6] + (n mod 6)/2 for even n ≥ 12.