In 1992, Heath, Leighton, and Rosenberg asked: Which is more powerful for laying out graphs, stacks or queues? They formalized this question by introducing the stack number and queue number of graphs. We give the following partial answer to this question: Not stacks.

More specifically, we describe an infinite family of graphs all having queue number at most 4 but having unbounded stack number. The proof of this result uses only basic combinatorics (the Pigeonhole Principle and the Erdös-Szekeres Theorem) and the well-known Hex Lemma.

This is joint work with Vida Dujmović, David Eppstein, Robert Hickingbotham, and David Wood.