Maximal Rectilinear Crossing of Cycles
W. H. Furry, Daniel J. Kleitman · Studies in Applied Mathematics · 1977
We address the following question: In drawing a cycle on n vertices (or a graph all of whose degrees are 2) in the plane with straight line arcs, how many crossings can there be? A complete answer is given; namely, if n is odd, the number of crossings can be anything up to n(n−3)/2 except n(n−3)/2−1. For n even, the number of crossings in one cycle can be any integer up to n(n−4)/2+1; general bivalent even graphs can achieve any integer up to n(2n−7)/4 as the number of crossings.