The Maximum of the Maximum Rectilinear Crossing Numbers of $d$-Regular Graphs of Order $n$

Abstract

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 Furry and Kleitman as partial results in the direction of this conjecture.