The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\) (Q1028834)

Summary: We extend known results regarding the maximum rectilinear crossing number of the cycle graph (\(C_n\)) and the complete graph (\(K_n\)) to the class of general \(d\)-regular graphs \(R_{n,d}\). We present the generalized star drawings of the \(d\)-regular graphs \(S_{n,d}\) of order \(n\) where \(n+d\equiv 1 \pmod 2 \) and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of \(S_{n,d}\) for \(n \equiv d \equiv 0 \pmod 2\) is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by \textit{W.H. Furry} and \textit{D.J. Kleitman} [``Maximal rectilinear crossing of cycles'', Studies appl. Math. 56, 159--167 (1977; Zbl 0349.05104).] as partial results in the direction of this conjecture.