On the Stable Crossing Number of Cubes
Paul C. Kainen · Proceedings of the American Mathematical Society · 1972
Very few results are known which yield the crossing number of an infinite class of graphs on some surface. In this paper it is shown that by taking the class of graphs to be d-dimensional cubes $Q(d)$ and by allowing the genus of the surface to vary, we obtain upper and lower bounds on the crossing numbers which are independent of d. Specifically, if the genus of the surface is always $\gamma (Q(d)) - k$, where $\gamma (Q(d))$ is the genus of $Q(d)$ and k is a fixed nonnegative integer, then $4k \leqq \operatorname {cr}_{\gamma (Q(d)) - k} (Q(d)) \leqq 8k$ provided that k is not too large compared to d.