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

Theorems

Any connected planar graph with n vertices, m edges and f faces satisfies n-m+f=2.
More generally, any planar graph of c components satisfies n-m+f-c=1 [7].

A graph is planar if and only if it does not contain a subgraph homeomorphic to either K₅ or K_3,3 [5].

For any graph of n vertices and maximum degree at most d, the Palm Trees algorithm with Alternative Final Loop finds an induced palm tree of at least 3n/(d+(5/3)) vertices.

(For further information see my thesis).