Maximum planar subgraph problem

Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid).

Is there any library in python for finding the maximum planar subgraph?

Is there some way how to implement these constraints for the grid graph?

Edit: As I understood I am looking for the maximum planar subgraph which is at most 4-connected and at least 2-connected

• Induced subgraph? What about the $n \times 1$ subgraph? Dec 8 '21 at 17:53
• Are you allowed to delete edges, or only vertices? Dec 8 '21 at 17:54
• Check out the crossing number of a graph. Dec 8 '21 at 17:54
• PS, the maximum planar subgraph problem is NP-hard. Dec 8 '21 at 18:09
• It is the opposite of an induced subgraph - i am not allowed to delete vertices, only edges. The crossing number should go to zero. I know - MSP is NP hard, but isnt there any approximation? Dec 8 '21 at 22:09

I doubt there are any implementations for the algorithms you are looking for.

The problem, also known as Planar Edge Deletion, Edge Planarization, Graph Planarization, or sometimes Minimum Planarization, is NP-complete and was shown in 2007 to be fixed-parameter tractable (for every fixed number of edges you want to delete, there is a "linear time algorithm" for the problem). However, the algorithm is extremely non-trivial and rely on deep mathematical results.

* K. Kawarabayashi and B.A. Reed. Computing crossing number in linear time. In: Proc. STOC 2007, 382—390.

• Where is here the connection to the grid graph (3 or 4 connected graph) Jan 4 at 17:08

This doesn't answer your question about your particular problem, but you can find theory for a related problem involving grids by searching for "bidimensionality".

It's the idea that every graph is either low treewidth or contains a large grid minor which makes it possible to get solution in polynomial time.

See Section 3 in Beyond Planar Graphs presentation by DeMaine. Also this is mentioned in Section 1 of Width parameters beyond tree-width and their applications, which is a good tutorial for the basics needed to understand bidimensionality results.

• Minors and subgraphs are very different, though. Also, you don't actually find a grid minor when applying bidimensionality, you only conclude that it exists and then you return a correct answer based on that knowledge. Jan 10 at 18:47
• Thanks for the correction, edited the post Jan 10 at 23:02
• Not sure yet this will help, but I appreciate your help:) Jan 11 at 9:07