Planarization and
Fragmentability of Some Classes of Graphs
K Edwards and G E Farr
ABSTRACT
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 fragmentability 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 proporation of vertices that must be removed
from a graph of average degree at most d in order to leave behind a planar
subgraph is at most (d-2)/(d+1), provided d > = 4 or the graph
is connected and d > =
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.