The crossing number of chordal ring networks

The chordal ring network of order n, denoted by CR_n (x,y,z), is the graph with vertex set Z_n, an additive group of integers modulo n, and adjacencies given by i ∼ i+x, i ∼ i+y, i ∼ i+z for all even vertex i and distinct odd integers x, y, z in [1, n-1]. 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. From this perspective, the analysis of crossing numbers of graphs makes most sense when one focuses on networks(graphs) that have good properties as interconnection networks. In this paper, we study the crossing number of the chordal ring networks CR_n (1, 3, 9) for all even n ≥ 10.