A better approximation algorithm for finding planar subgraphs

The MAXIMUM PLANAR SUBGRAPH problem given a graphG, find a largest planar subgraph ofG has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time approximation algorithm for this NP-Complete problem was known to ...

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G'. In this case G' is said to be a maximum planar induced subgraph of G. We ...