The Maximum Induced Planar Subgraph problem

Abstract: The Maximum Induced Planar Subgraph problem asks

for the largest set of vertices in a given input graph G

that induces a planar subgraph of G. Equivalently, we may

ask for the smallest set of vertices in G whose removal

leaves behind a planar subgraph. This problem has been

linked by Edwards and Farr to the problem of _fragmentability_

of graphs, where we seek the smallest proportion of vertices

in a graph whose removal breaks the graph into small (bounded

size) pieces. This talk describes some algorithms

developed for this problem, together with theoretical and

experimental results on their performance. The material

presented is joint work either with Keith Edwards (Dundee)

or Kerri Morgan (Monash).