# 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  and  (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