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

Improve this question
$\endgroup$
5
  • $\begingroup$ Induced subgraph? What about the $n \times 1$ subgraph? $\endgroup$
    – John Kemeny
    Commented Dec 8, 2021 at 17:53
  • 1
    $\begingroup$ Are you allowed to delete edges, or only vertices? $\endgroup$
    – John Kemeny
    Commented Dec 8, 2021 at 17:54
  • $\begingroup$ Check out the crossing number of a graph. $\endgroup$
    – John Kemeny
    Commented Dec 8, 2021 at 17:54
  • $\begingroup$ PS, the maximum planar subgraph problem is NP-hard. $\endgroup$
    – John Kemeny
    Commented Dec 8, 2021 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
    Commented Dec 8, 2021 at 22:09

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Where is here the connection to the grid graph (3 or 4 connected graph) $\endgroup$
    – nuemlouno
    Commented Jan 4, 2022 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.

Improve this answer
$\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$
    – John Kemeny
    Commented Jan 10, 2022 at 18:47
  • $\begingroup$ Thanks for the correction, edited the post $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 10, 2022 at 23:02
  • $\begingroup$ Not sure yet this will help, but I appreciate your help:) $\endgroup$
    – nuemlouno
    Commented Jan 11, 2022 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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