Planarization and fragmentability for graphs of bounded degree

Graham Farr
School of Computer Science and Software Engineering Monash University, Victoria, Australia

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.

(Joint work with Keith Edwards, University of Dundee.)