3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Induced subgraph? What about the $n \times 1$ subgraph? $\endgroup$
    – Pål GD
    Dec 8 '21 at 17:53
  • 1
    $\begingroup$ Are you allowed to delete edges, or only vertices? $\endgroup$
    – Pål GD
    Dec 8 '21 at 17:54
  • $\begingroup$ Check out the crossing number of a graph. $\endgroup$
    – Pål GD
    Dec 8 '21 at 17:54
  • $\begingroup$ PS, the maximum planar subgraph problem is NP-hard. $\endgroup$
    – Pål GD
    Dec 8 '21 at 18:09
  • $\begingroup$ 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? $\endgroup$
    – nuemlouno
    Dec 8 '21 at 22:09
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Where is here the connection to the grid graph (3 or 4 connected graph) $\endgroup$
    – nuemlouno
    Jan 4 at 17:08
0
+100
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jan 10 at 18:47
  • $\begingroup$ Thanks for the correction, edited the post $\endgroup$ Jan 10 at 23:02
  • $\begingroup$ Not sure yet this will help, but I appreciate your help:) $\endgroup$
    – nuemlouno
    Jan 11 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.