In 1992, Heath, Leighton, and Rosen­berg asked: Which is more pow­er­ful for lay­ing out graphs, stacks or queues? They for­mal­ized this ques­tion by in­tro­duc­ing the stack num­ber and queue num­ber of graphs. We give the fol­low­ing par­tial an­swer to this ques­tion: Not stacks.

More specif­i­cally, we de­scribe an in­fi­nite fam­ily of graphs all hav­ing queue num­ber at most 4 but hav­ing un­bounded stack num­ber. The proof of this re­sult uses only basic com­bi­na­torics (the Pi­geon­hole Prin­ci­ple and the Erdös-Szek­eres The­o­rem) and the well-known Hex Lemma.

This is joint work with Vida Du­j­mović, David Epp­stein, Robert Hick­ing­botham, and David Wood.