# Converting a non-planar graph to planar

Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness.

Besides connectedness, $G$ is guaranteed to have enough connectivity so that removal of a reasonably small amount of vertices do not disconnect the graph and there are several paths between two specified vertices (removing one or two vertices do not let $G$ be a tree).

I have looked it up on the Internet and could not find any research. Maybe it is because I do not know the proper keywords.

Is there any research on this topic? If so, could you provide a reference?

• Google for "maximum planar subgraph". – adrianN Jun 17 '16 at 9:38
• Is maintaining connectedness your only criterion? If so, any spanning tree is an answer to your question (every tree is planar) and there are well-known algorithms for computing those. – David Richerby Jun 17 '16 at 9:54
• @DavidRicherby That is a crucial point I failed to clarify in my question. Thank you for noticing. I am studying on disjoint paths problem in planar graphs. Therefore, finding a spanning tree would not help me. – padawan Jun 17 '16 at 10:18

In other words, you seem to be interested in both planar vertex deletion and planar edge deletion. For starters, you can see [1] and [2] (the problems seem FPT parameterized by the number of operations $k$).
• @cagirici Glad to be of help! A graph is an apex graph if you can turn it into a planar graph by deleting a single vertex (for $k$-apex graphs, you get the same result by removing $k$ vertices). There's a Wikipedia article on apex graphs that has information that could be of further help. – Juho Jun 17 '16 at 10:22