Unfortunately, finding the planar subgraph with the maximum possible number of edges (the maximum planar subgraph problem[3]) is NP-hard, and MaxSNP-hard, implying that there probably does not exist a polynomial time algorithm that solves the problem exactly or that approximates it arbitrarily well.
A better approximation ratio, 9/4, is known, based on a method for finding a large partial 2-tree as a subgraph of the given graph.
[1][4] Alternatively, if it is expected that the planar subgraph will include almost all of the edges of the given graph, leaving only a small number k of non-planar edges for the incremental planarization process, then one can solve the problem exactly by using a fixed-parameter tractable algorithm whose running time is linear in the graph size but non-polynomial in the parameter k.[5] The problem may also be solved exactly by a branch and cut algorithm, with no guarantees on running time, but with good performance in practice.
[8] Edwards & Farr (2002) proved a tight bound of 3n/(Δ + 1) on the size of the largest planar induced subgraph, as a function of n, the number of vertices in the given graph, and Δ, its maximum degree; their proof leads to a polynomial time algorithm for finding an induced subgraph of this size.
[2] Fixing the embedding of the planarized subgraph is not necessarily optimal in terms of the number of crossings that result.