Planarization and fragmentability of some classes of graphs

The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give firagmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of k-colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most (d) over bar in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most ((d) over bar - 2)/((d) over bar + 1), provided (d) over bar >= 4 or the graph is connected and (d) over bar >= 2. The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. (C) 2007 Elsevier B.V. All rights reserved.