×

Bounds for the crossing number of the N-cube. (English) Zbl 0722.05028

Let \(Q_ n\) denote the n-dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number \(\nu (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 \(\nu (Q_ n)<\frac{1}{6}N^ 2\). For the lower bound we prove that \(\nu (Q_ n)=\Omega (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 \(\nu (Q_ n)=\Omega (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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke, J. Graph Theory 4 pp 145– (1980)
[2] Chung, SIAM J. Alg. Disc. Meth. 8 pp 33– (1987)
[3] Erdös, Am. Math. Month. 80 pp 52– (1973)
[4] Garey, SIAM J. Alg. Disc. Meth. 4 pp 312– (1983)
[5] and , Mathematics for the Analysis of Algorithms, 2nd ed. Birkhäuser (1982).
[6] Crossing numbers of graphs. Graph Theory and Applications. Lecture Notes in Mathematics 303, Springer-Verlag, New York (1972) 111–124.
[7] Graph Theory. Addison-Wesley, Reading, MA (1969).
[8] Kleitman, J. Combinat. Theory 9 pp 315– (1970)
[9] Topics in Number Theory, Vol. 1. Addison-Wesley, Reading, MA (1965).
[10] and , Topological graph theory. Selected Topics in Graph Theory 1. Academic Press, London (1978) 15–49.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.