Two seminars by
Dr Graham Farr, School of Computer Science and Software Engineering, Monash University, Victoria, Australia
FRAGMENTABILITY OF CLASSES OF GRAPHS

Abstract: 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.

This is joint work with Keith Edwards, University of Dundee.
PLANARIZATION AND FRAGMENTABILITY FOR GRAPHS OF BOUNDED DEGREE

Abstract: We describe an algorithm which, for a graph with n vertices and maximum degree d, finds a set of at most n (d-2)/(d+1) vertices whose removal leaves behind a planar graph. (This is thus a heuristic for the Maximum Induced Planar Subgraph problem). For d <= 3, this performance guarantee is, in a sense, best possible. We prove that it performs as claimed. Later, some connections will be made with work on fragmentability discussed in my previous talk, but it is not necessary to have attended that talk.

This is joint work with Keith Edwards, University of Dundee.

These seminars were held at the Department of Computer Science/Department of Mathematics, Royal Holloway, University of London on 30 April and 1 May 2001 respectively.

back