Seminar series
Date
Tue, 29 Jan 2008
13:30
13:30
Location
L3
Speaker
Graham Farr
Organisation
Monash University
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).