Bounds for the crossing number of the N ‐cube
Tom Madej · Journal of Graph Theory · 1991
Abstract Let Q n denote the n‐dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number v ( Q n ), i.e., the minimum number of edge‐crossings in any planar drawing of Q n . The upper bound is close to a result conjectured by Eggleton and Guy and the lower bound is a significant improvement over what was previously known. Let N = 2 n be the number of vertices of Q n . We show that v ( Q n ) 0 is a constant and lg is the logarithm base 2. The best lower bound using standard arguments is v ( Q n ) = Ω( N (lg N ) 2 ). The lower bound is obtained by constructing a large family of homeomorphs of a subcube with the property that no given pair of edges can appear in more than a constant number of the homeomorphs.