The maximum planar subgraph problem (i.e given a graph, find its subgraph which is planar and has the maximum number of edges) is NP hard and MaxSNP hard (as per wikipedia) and we do not have a polynomial time algorithm that solves the problem exactly.
I was wondering whether assuming that the graph is bipartite makes the problem any more tractable. I couldn't find any links online for this so was wondering if anyone knows.
Specifically, my questions are ->
- For the problem of finding the maximum planar subgraph of a bipartite graph, are there any polynomial algorithms which can solve this exactly?
- Are there any links to articles/papers that address this problem?
- Are there papers that address the maximum planar subgraph problem for other special classes of graphs?
Best Answer
The general case of this problem can be reduced to the bipartite case, so the bipartite case must also be NP hard (and all the other kinds of hard that the general case is).
The reduction is as follows. Suppose we have an $n$-vertex, $m$-edge graph $G$. We define an $(n+m)$-vertex, $2m$-edge bipartite graph $G'$ by subdividing each edge of $G$ once. (This is bipartite because we can put all the original vertices in one part, and all the subdividing vertices in the other part.)
Say that edge $vw$ in $G$ gets subdivided into two edges $v x_{vw}$ and $x_{vw} w$ in $G'$. Any maximal planar subgraph of $G'$ must certainly use at least one of the two edges $v x_{vw}$, $x_{vw} w$: if neither edge is part of a planar subgraph, we can always add either one of them without losing planarity. For some cases, the largest planar subgraph will use both edges.
So there is a correspondence between maximal planar subgraphs of $G$, and maximal planar subgraphs of $G'$:
Therefore finding the largest planar subgraph of $G'$ is just as hard as finding the largest planar subgraph of $G$.