Premium
Bounds for the crossing number of the N ‐cube
Author(s) -
Madej Tom
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150109
Subject(s) - combinatorics , upper and lower bounds , mathematics , hypercube , logarithm , constant (computer programming) , cube (algebra) , discrete mathematics , mathematical analysis , computer science , programming language
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 ) < 1/6 N 2 . For the lower bound we prove that v ( Q n ) = Ω( 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 ( 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.