Premium
The Same Upper Bound for Both: The 2‐page and the Rectilinear Crossing Numbers of the n ‐Cube
Author(s) -
Faria Luerbio,
de Figueiredo Celina M. H.,
Richter R. Bruce,
Vrt'o Imrich
Publication year - 2016
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.21910
Subject(s) - cube (algebra) , combinatorics , mathematics , upper and lower bounds , crossing number (knot theory) , discrete mathematics , mathematical analysis , cartography , intersection (aeronautics) , geography
We present two main results: a 2‐page and a rectilinear drawing of the n ‐dimensional cube Q n . Both drawings have the same number125 768 4 n − 2 n − 3 3 ( 3 n 2 + 9 + ( − 1 ) n + 12 )of crossings, even though they are given by different constructions. The first improves the current best general 2‐page drawing, while the second is the first nontrivial rectilinear drawing of Q n .