|
The Maximum Induced Planar Subgraph Problem (MIPS) is the task of finding the largest subset of vertices in a graph that induce a planar subgraph. This problem is known to be NP-hard [6].
In this project several new approximation algorithms for the Maximum Induced Planar Subgraph and Maximum Induced Outerplanar Subgraph problems were designed. One of these algorithms was shown to produce an induced outerplanar subgraph of size at least 3n/(d+(5/3)) for graphs of maximum degree at most d. Both new and existing algorithms were implemented and their behaviour in terms of running time and performance observed on over 12,000 randomly generated graphs. Experimental results indicate that the size of the induced outerplanar subgraphs produced were often larger than the induced planar subgraphs produced by the existing algorithms for MIPS.
A further algorithm was designed that identifies vertices that can be added to an induced planar subgraph whilst maintaining planarity. This algorithm was used in conjunction with other algorithms to produce induced planar subgraphs of a size larger than those produced by existing algorithms.
|