Another of my Graph Drawing papers is online today: "Planar Induced Subgraphs of Sparse Graphs", arXiv:1408.5939, with Cora Borradaile and her student Pingan Zhu. It's about finding large planar subgraphs in arbitrary graphs; in the version of the problem we study, we want the planar subgraph to be an induced subgraph, so the goal is to find as large a subset of vertices as possible with the property that all edges connecting them can be drawn planarly. Equivalently, we want to delete as few vertices as possible to make the remaining graph planar. It's NP-complete, of course, so our goal is to prove good bounds on how many vertices you need to delete rather than computing this number exactly.

We were inspired to look at this sort of problem by a 2001 paper of Alon, Mubayi, and Thomas, who proved among other things that in triangle-free graphs with \( m \) edges you can delete \( m/4 \) of the vertices and eliminate all the cycles in the graph (so the remaining graph is a forest). We knew also (too easy for a publication) that you can delete \( m/3 \) vertices and get a linear forest, delete \( m/2 \) vertices and get a matching, or delete \( m/1 \) vertices and get an independent set. So we were hoping that this would be part of a hierarchy of graph classes, sort of like the hierarchy coming from the Colin de Verdière graph invariant: delete \( m/5 \) vertices and get an outerplanar graph, delete \( m/6 \) vertices and get a planar graph, delete \( m/7 \) vertices and get...I don't know, some interesting class of nonplanar graphs. It didn't quite work out that way.

We did get one result sort of in this vein: you can delete \( m/5 \) vertices and get a partial 2-tree. And this is in some sense optimal, because there are graphs (such as \( K_5 \)) for which that's the biggest partial 2-tree you can get. But then fractional divisors started turning up: you can delete \( m/4.5 \) vertices and get a pseudoforest (again optimal). And the best we could get for finding planar subgraphs was even messier (and used linear programming to work out the precise bounds): you can delete \( 23m/120 \) (around \( m/5.22 \)) vertices and get a planar graph. Probably not optimal.

Ok, so the idea of getting a hierarchy with integer divisors is dead, but maybe there's still a hierarchy, just with messier numbers. Maybe, but if you want minor-closed graph families (as all the above ones are) then the divisors can't get arbitrarily big: if you choose a divisor \( k \) that's bigger than six, then no matter how you try to delete \( m/k \) vertices, the smallest minor-closed family you can get will be the class of all graphs. The proof involves the existence of 3-regular cages, sparse graphs without any short cycles: if you start with a cage, and don't delete enough vertices, you'll get a graph that still has high girth and high cyclomatic number. The high girth can be used to contract a lot of edges without introducing any self-loops or multiple adjacencies, giving a much denser minor of the remaining graph, dense enough that it necessarily has large clique minors.

Maybe there's some way of rescuing the idea of a hierarchy of subgraph classes by using classes of graphs that aren't closed under minors, but have weaker sparsity properties, such as the 1-planar graphs? I don't know; that's as far as we were able to prove. But it might be an interesting subject for future research.