Hex, books, and queues
My latest preprint is “Stack-number is not bounded by queue-number”, arXiv:2011.04195, with Vida Dujmović, Robert Hickingbotham, Pat Morin, and David R. Wood; Hickingbotham is a postgraduate student of Wood at Monash University. It solves a question implicit in the work of Heath, Leighton and Rosenberg (1992) on whether graphs of bounded queue number have bounded stack number (they don’t), disproves a conjecture of Blankenship and Oporowski (1999) on whether subdividing a graph of unbounded stack number can reduce its stack number to bounded (it can), and answers a question of Bonnet, Geniet, Kim, Thomassé, and Watrigant (to appear at SODA 2021) on whether graphs of unbounded stacknumber can have bounded sparse twin-width (they can). And it does so in part using an old trick from combinatorial game theory from a mathematician who won a Nobel prize for his work in game theory. But what are stack number and queue number? And what could combinatorial games possibly have to do with these sorts of questions in structural graph theory?
The game in question is Hex, in which two players take turns placing their stones on hexagonal cells connected into a triangular grid and arranged in a rhombus. Each player tries to form a path of stones connecting two sides of the rhombus while simultaneously trying to block the other player from making a path. The rendering below from HexWiki shows a Hex board with a game in progress:
In tic-tac-toe, a similar game on a square grid, both players can end up blocking each other, producing a drawn game. But as John Nash famously proved in 1952, this can’t happen in Hex: every game ends with one or the other player forming a path. This inability to draw is usually explained as a topological property of disks in the plane, equivalent to the Brouwer fixed-point theorem, although it also has a simple combinatorial proof involving walking along the boundary between the two colors of stones on a filled board, starting from a corner of the rhombus, and observing that the walk can only end at a non-opposite corner. But the lack of draws also implies the following statement about graphs: if you form a large triangular grid (the graph of positions and adjacencies of stones in Hex), and label its vertices with two colors (the colors of the stones of the two Hex players), then it must contain a long path: at least long enough to reach from one side of the Hex board to the other.
The same combinatorial proof for the Hex board works for any planar triangulation of a disk whose boundary can be divided into four paths with opposite pairs of paths far apart. Even some outerplanar graphs have the same long-path property. Suppose, for instance, that an outerplanar triangulated disk has a complete binary tree for its dual graph. Then we can form a long path by starting at a vertex of the root triangle and repeatedly walking down the tree, at each step moving to a neighbor of the same color whose triangle is closest in the dual tree. This walk takes a long step (such as the step on the top edge of the red path shown below) only when stepping from a vertex whose neighbors include a long path of the other color (the blue path shown below), and otherwise it takes many steps.
On the other hand, the square grid or other bipartite graphs don’t have the long path property, because if you color them bipartitely then there are no nontrivial monochromatic paths. Neither do subcubic graphs, because their maximum cuts always partition them into two subsets whose longest path has length at most one. The Hex board graph turns out to be the right choice for our purposes, because as well as the long path property it has bounded degree (unlike the outerplanar example) and a nice regular planar structure making stack and queue layouts easy.
So what are these layouts? Stack layout is another name for book embedding, in which the vertices of a graph are arranged in a line and its edges are placed without crossings into “pages”, half-planes bounded by the line. If you traverse the vertices of the graph in the order of the line, add an edge to its page when you traverse its first endpoint, and remove an edge from the page when you traverse the second endpoint, then the order of additions and removals is last-in-first-out, the same as a stack. The stack number or book thickness is the smallest number of pages you need to construct a layout like this. Below is an example I’ve used before, a 3-page book embedding of the complete graph \(K_5\), whose stack number is three:
If you replace the last-in-first-out ordering of additions and removals in a stack by first-in-first-out ordering, you get a queue. So a queue layout is just an ordering of the vertices into a line, and a partition of the edges into “pages”, so that the traversal of the vertices by their line order produces a queue ordering of additions and removals of edges within each page. As Auer et al described at GD 2010, these layouts can also be described topologically, by representing each page as a cylinder with the line going longitudinally along it, and requiring each edge to be placed in such a way that it loops all the way around the cylinder. The queue number is the minimum number of these queues, or cylindrical pages, that you need to organize the graph in this way. It’s also closely related to the compact layout of graphs in 3d.
Below is an example I recently drew for a new Wikipedia article on shuffle-exchange networks. These are very nonplanar graphs, but the layout shown can almost be drawn without crossings on two cylinders (one for the edges that bend around the left side of the vertices, another for the edges on the right) or on a single surface with a figure-eight cross-section, formed by gluing two cylinders together on a line. However, this only takes care of the curved edges. If you look closely, there are also short horizontal edges between consecutive vertices, which in a queue layout would need to wrap around another third cylinder. So these graphs have queue number at most three.
With all that as background, the central example in our new preprint is the Cartesian product of a triangular grid with a star. It looks like this, but possibly with a bigger grid or star:
The reason Cartesian products are useful in this context is that they behave nicely for queue layouts but not quite as nicely for stack layouts. If two graphs \(G\) and \(H\) both have queue layouts with a bounded number of queues, and in addition the layout of \(H\) is strict, meaning that within each page, each vertex has at most one earlier and one later neighbor, then we can lay out their product by grouping the vertices of the product into copies of \(G\) and placing each copy separately, with the order of the copies determined by the layout of \(H\). The resulting layout will still have a bounded queue number. The star has bounded queue number, but its layouts are not strict, because it has high degree at the center of the star. As a planar graph the triangular grid has bounded queue number, and because it also has bounded degree its layouts can be made strict. Therefore, the product graph again has bounded queue number.
For stack layouts, a similar product layout works, but only when \(H\) is bipartite. We can reverse the ordering within the copies of \(G\) coming from one side of the bipartition, and the edges going from one copy to another will still be stack-ordered. But when \(H\) is not bipartite, there is no way to consistently choose which copies of \(G\) to reverse. The long path property of Hex boards, in some sense, provides a quantitative measure for the fact that their graphs are far from being bipartite.
Of course, this only shows that a certain stack layout doesn’t work, not that all layouts fail. Our proof that all stack layouts of our product graph fail proceeds in a sequence of reductions in which we assume we are given a layout, and successively reduce it to more-constrained layouts on smaller graphs until reaching a contradiction. The first reductions use the pigeonhole principle to find products of the grid with a smaller star, in which all leaf copies of the grid have the same layout. Next we use the Erdős–Szekeres theorem to find a product with an even smaller star, in which each copy of the star is consistently ordered by the layout in one of two ways. Finally, we use the result about long paths in Hex to find a product of this small star with a path, in which all copies of the star are consistently ordered in the same way, and prove that this ordering of this graph cannot have a bounded stack number.
Heath, Leighton and Rosenberg introduced both stack number and queue number in their 1992 work, and provided an example for which the stack number is exponentially bigger than the queue number, naturally raising the question whether even bigger separations are possible. Our work settles this question by showing that there is no function (exponential or otherwise) that can be used to bound stack number as a function of queue number. In the opposite direction, Heath, Leighton & Rosenberg conjectured that queue number cannot be made to grow significantly more quickly than stack number, but this remains open.
In 1999, Blankenship and Oporowski observed that subdividing the edges of a graph can lead to better stack layouts: for instance adding a single subdivision point to each edge of a complete graph reduces the stack number from linear to the square root of the number of vertices. They conjectured that this improvement cannot be too extreme: reducing the stack number from non-constant to constant should require a non-constant number of subdivision points. Our example disproves the Blankenship–Oporowski conjecture. The star-triangular grid product graph has non-constant stack number, but because it has bounded queue number its subdivisions with three subdivision points per edge have bounded stack number, according to a result of Dujmović and Wood (2005). The same paper of Dujmović and Wood also stated the question of whether stack number can be bounded by a function of queue number more explicitly.
The definition of twin-width is too technical to summarize here; see the forthcoming SODA paper by Bonnet et al., which shows among other results that it is bounded for graphs of bounded stack number. Our results show that this is not an equivalence: there exist graphs (including the star-triangular grid products) that have unbounded stack number, but still have bounded sparse twin-width.