Fragmentability of classes of graphs
Graham Farr
School of Computer Science and Software Engineering
Monash University, Victoria, Australia
We introduce the notion of fragmentability, which
measures how easily the graphs in some class can be
broken up into small (bounded size) pieces by removal of vertices.
We focus on the proportion of vertices removed, rather than the
difficulty of finding those vertices.
We are particularly interested in classes of graphs of bounded
degree, and find upper and lower bounds for such classes.
The upper bound is obtained from an algorithm for obtaining a large
induced planar subgraph of a graph.
(Joint work with Keith Edwards, University of Dundee.)