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.)