Graham Farr Associate Professor
School of Information Technology
Monash University Australia

The Maximum Induced Planar Subgraph Problem

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.  It is also related to the classical Maximum Planar Subgraph problem which is of central importance in graph layout algorithms.  This talk describes some algorithms developed for this problem, together with theoretical and experimental results on their performance.  Most of the algorithms presented are joint work either with Keith Edwards (Dundee) or Kerri Morgan.  The experimental analysis was done by Morgan.