The Maximum Rectilinear Crossing Number of the n Dimensional Cube Graph

Authors

Matthew Alpert, Harvard University
Elie Feder, CUNY Kingsborough Community CollegeFollow
Heiko Harborth, Technische Universitat Braunschweig
Sheldon Klein, Rambam Mestiva High School

Document Type

Article

Publication Date

3-25-2009

Abstract

We find a.nd prove the maximum rectilinear crossing n1.1mber of the three-dimensional cube graph (Q₃). We demonstrate a method of drawing then-cube graph, Q_n., with many crossings, and thus find a lower bound for the maximum rectilinear crossing number of Q_n. We conjecture that this bound is sharp. We also prove an upper bound for the maximum rectilinear crossing number of Q_n.

Comments

This work was originally published in Congressus Numerantium.