FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 11, 14:30 ~ 15:00 - Room B11
Improved upper bounds on the crossing number, the 2-page crossing number and the rectilinear crossing number of the hypercube
Celina Figueiredo
UFRJ, Brazil - celina@cos.ufrj.br
The $n$-cube $Q_n$ has as vertices all binary strings of length $n$, and there is an edge between two strings if and only if they differ in precisely one position. Very little is known about exact values of the crossing number (the minimum number of crossings in a drawing in the plane), the 2-page crossing number, and the rectilinear crossing number for $Q_n$. We exhibit drawings that are in line with the crossing number conjecture of Erdős and Guy. We also exhibit 2-page and rectilinear drawings, surprisingly with the same number of crossings, despite being completely different constructions.
Joint work with Luerbio Faria (State University of Rio de Janeiro, Brazil), Ondrej Sýkora (Loughborough University, UK), Imrich Vrt'o (Slovak Academy of Sciences, Slovak Republic) and Bruce Richter (University of Waterloo, Canada).