The Analysis and Design of Approximation Algorithms for the Maximum Induced Planar Subgraph Problem

Some of the main achievements in this project include:

• best known approximation algorithms for the Maximum Induced Outerplanar Subgraph (MIOPS) problem;

• mathematical analysis of a new algorithm for MIOPS to show that the subgraphs produced contain at least 3n/(d+(5/3)) vertices for graphs of maximum degree at most d;

• several new approximation algorithms for the Maximum Induced Planar Subgraph problem (MIPS);

• implementation of both new and existing algorithms;

• experimental results giving the average performance and time complexity of all algorithms;
  (See Appendix C in thesis)

• experimental evidence that the new algorithms for MIOPS problem found subgraphs of comparable (or larger) size to those found by existing algorithms;

• an algorithm for adding vertices to an existing subgraph whilst preserving planarity, which in conjunction with algorithms such as those designed for MIOPS produced a larger subgraph than all existing algorithms for MIPS.