Abstrakt
A queue layout of a graph consists of a linear ordering $\sigma$ of its vertices and a partition of its edges into sets, called queues, such that in each set no two edges are nested with respect to $\sigma$. We show that the n-dimensional hypercube Qn has a layout into $n-\lfloor \log_2 n \rfloor$ queues for all $n \ge 1$.
On the other hand, for every $\epsilon>0$, every queue layout of Qn has more than $(1/2-\epsilon) n-O(1/\epsilon)$ queues and, in particular, more than (n-2)/3 queues. This improves previously known upper and lower bounds on the minimal number of queues in a queue layout of Qn.
For the lower bound we employ a new technique of out-in representations and contractions which may be of independent interest.