Using incremental planarization for graph drawing is most effective when the first step of the process finds as large a planar graph as possible. Unfortunately, finding the planar subgraph with the maximum possible number of edges (the
maximum planar subgraph problem) 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. In an
n-vertex
connected graph, the largest planar subgraph has at most 3
n − 6 edges, and any
spanning tree forms a planar subgraph with
n − 1 edges. Thus, it is easy to approximate the maximum planar subgraph within an
approximation ratio of one-third, simply by finding a spanning tree. 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. 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. This parameter
k is known as the
skewness of the graph. There has also been some study of a related problem, finding the largest planar
induced subgraph of a given graph. Again, this is NP-hard, but fixed-parameter tractable when all but a few vertices belong to the induced subgraph. proved a tight bound of 3
n/(Δ + 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. ==Adding edges to a planarization==