Grid majors
I’ve written here about grid minors before, more than once. These are grid graphs that you can get from a given graph \(G\) as a minor (that is, by removing edges or vertices from \(G\) and contracting others of its edges). So, in the other direction, a “grid major” of \(G\) must be a grid graph that has \(G\) as a minor. These are the subject of my new preprint, “Homotopy height, grid-major height and graph-drawing height” (arXiv:1908.05706, with Therese Biedl, Erin Chambers, Arnaud De Mesmay, and Tim Ophelders, to appear at Graph Drawing).
You can define the terms in the paper’s title for any planar graph, but our results are cleanest for maximal planar graphs. If we define the height of a grid to be the smaller of its two dimensions, then the grid-major height of a graph \(G\) is just the smallest height of a grid that has \(G\) as a minor. The detailed definition of homotopy height is trickier to explain, but the rough idea is that (after choosing one face of your graph to be the outer one) you should sweep a path from one edge of the outer face, across the graph, to another edge of the outer face, trying as you do to keep the path as short as possible. Paths can move across triangular faces (changing the number of vertices by \(\pm 1\)) or path vertices can “slide” along edges (leaving the total number unchanged. The smallest length \(\ell\) such that you can do this sweep and always maintain length at most \(\ell\) turns out to equal the grid-major height, and both are lower bounds on the height of a conventional drawing of the graph (with its vertices at grid points and its edges as straight line segments).
For instance, the following drawing shows a height-\(3\) grid drawing of a maximal planar graph, a sequence of \(5\) paths of length at most \(3\) sweeping from the left to the right edge of the graph, and the subsets of vertices to contract in a \(3\times 5\) grid to produce the graph as a minor. Each column of the grid has the same vertices as the corresponding path in the walk. For this graph, the drawing height, homotopy height, and grid-major height are all equal, but it is possible for the drawing height to be much larger than the other two quantities.
Both homotopy height and grid-major height come in simple and non-simple variations. They are equal for both variations, and both variations give a valid lower bound on graph drawing height. In simple homotopy height the swept path is required to stay simple (as it is in the example here) while more generally we allow walks that can repeat vertices. (In particular they can have “spikes”, parts of paths that double back along a single edge.) Correspondingly, non-simple grid-major height does not restrict how \(G\) is formed as a minor of a grid while the simple variant requires the parts of the grid corresponding to a single vertex of \(v\) to be contiguous within each column of the grid (as they are in the example here).
Because grid-major height behaves nicely under graph minor operations, it is automatically fixed-parameter tractable, but in a non-uniform way. What this means is that for each \(h\) there are finitely many graphs that, when they are a minor of \(G\), prevent \(G\) from having grid-major height \(h\). We can find the grid-major height of \(G\) by looking for these “obstacles” and returning the smallest \(h\) for which no obstacles are found. And, whenever \(h\) is bounded, the time of the resulting algorithm is a polynomial whose exponent is independent of the size of \(G\). So an algorithm exists for any fixed \(h\), but we don’t know how to actually write it down as a program because we don’t know what the obstacles are or even whether the number of obstacles is computable.
Simple grid-major height is nicer from the algorithmic point of view, but still not entirely satisfactory. Our paper describes the existence of a simple grid major using the logic of graphs. When \(h\) is bounded this gives us a linear-time algorithm via Courcelle’s theorem. The algorithm could in principle be written out explicitly as a program, with \(h\) given as an input to the program rather than hardcoded into it. There is no problem with unknown lists of obstacles. But the logical description is huge and the dependence of Courcelle’s theorem on the size of the logical description is very high, so although the time is linear in the size of the graph it gets multiplied by a very quickly growing function of \(h\).