Bounds for the crossing number of the N-cube |
| |
Authors: | Tom Madej |
| |
Abstract: | Let Qn denote the n-dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number v(Qn), i.e., the minimum number of edge-crossings in any planar drawing of Qn. 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 = 2n be the number of vertices of Qn. We show that v(Qn) < 1/6N2. For the lower bound we prove that v(Qn) = Ω(N(lg N)c lg lg N), where c > 0 is a constant and lg is the logarithm base 2. The best lower bound using standard arguments is v(Qn) = Ω(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. |
| |
Keywords: | |
|
|