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'$:
- Given a maximal planar subgraph $H$ of $G$, subdivide its edges to get a subgraph of $G'$, and then add exactly one of the edges $v x_{vw}$ or $x_{vw} w$ (arbitrarily) for each edge $vw \notin E(H)$. If $H$ had $k$ edges, the result has $m+k$ edges.
- Given a maximal planar subgraph $H'$ of $G'$, take the subgraph of $G$ which has the edge $vw$ whenever $H'$ has both edges $v x_{vw}, x_{vw} w$. If $H'$ had $m+k$ edges, the result has $k$ edges.
Therefore finding the largest planar subgraph of $G'$ is just as hard as finding the largest planar subgraph of $G$.
Yes, they are (and well spotted).
Here's an old proof I have typed up. I think you can shorten it substantially however! To do so, I'd directly consider the walk bounding a face. It consists of alternating black / white vertices. Try argue using maximality that the walk is either a 4-cycle, or a star.
Lemma 1:
Every face of a 2-connected plane graph is bounded by a cycle.
This is well known (see, for example, Diestel)
Theorem 1:
Let $G$ be an mpb graph of minimum degree $\delta$ embedded in the plane. Then every face of $G$ is bounded by a 4-cycle if and only if $\delta \geq 2$.
Proof:
Let $G = (V,E)$ be an mpb graph and consider an embedding of $G$ in the plane. If every face of $G$ is bounded by a 4-cycle, then clearly $\delta \geq 2$. Conversely, assume $\delta \geq 2$. As $G$ is bipartite, $V$ can be partitioned into two sets, $B$ and $W$, such that every edge of $G$ is incident with one vertex of $B$ and one vertex of $W$.
First, we show that $G$ is 2-connected: Assume to the contrary, and without loss of generality, that $b_1\in B$ is a cut-vertex. Let $w_1, w_2$ be vertices of different components of $G-b_1$ such that $w_1, b_1, w_2$ are consecutive vertices of the walk bounding some face $f$ of $G$. As $w_1, w_2$ are adjacent to $b_1\in B$, it must be that $w_1, w_2 \in W$. Since the minimum degree of $G$ is at least 2, $w_2$ has a neighbour $b_2\in B$ such that $w_2, b_2$ are consecutive vertices of the walk bounding $f$. Since $b_2$ and $w_1$ are in different parts of the bipartition of $G$, and are both on the boundary of $f$, the maximality of $G$ implies that $w_1b_2 \in E$. Thus, $w_1, w_2$ lie in the same component of $G-b_1$, a contradiction. Hence $G$ is 2-connected.
We now show that every face of $G$ is a 4-cycle: Since $G$ is 2-connected and bipartite, by Lemma 1, every face is bounded by an even cycle. Thus it suffices to prove that every face of $G$ is bounded by a cycle of length less than 6. Assume, to the contrary, that some face $f$ of $G$ is bounded a cycle $C$ of length $k\geq 6$ and, without loss of generality, that $f$ is in the interior of $C$. Let $b_1, w_1, b_2, w_2, b_3, w_3$ be six consecutive vertices of $C$ with $b_1, b_2, b_3 \in B$ and $w_1, w_2, w_3 \in W$. As $b_1$ and $w_2$ lie on the same face and are in different parts of the bipartition of $G$, the maximality of $G$ implies that $b_1w_2 \in E$. Since the interior of $C$ is a face, $b_1w_2$ must lie in the exterior of $C$. Similarly to $b_1w_2$, the maximality of $G$ necessitates that $w_1b_3\in E$. If $w_1b_3$ lies inside $C$, it subdivides $f$, contradicting that $f$ is a face. If $w_1b_3$ lies outside $C$, it crosses $b_1w_2$, contradicting the planarity of $G$.
Theorem 2:
If $G$ is an mpb graph of minimum degree one, then $G$ is a star.
Proof:
Let $G = (V,E)$ be an mpb graph with partite sets $B$, $W$, and consider an embedding of $G$ in the plane. Without loss of generality, $v\in B$ is the neighbour of a vertex of degree 1. We claim that every neighbour of $v$ has degree 1. Assume to the contrary that $v$ has a neighbour of degree greater than 1. We can find neighbours $u,w$ of $v$ with $\text{deg}(u) = 1$ and $\text{deg}(w) \geq 2$ such that $u,v,w$ lie on the same face, $f$, of $G$. Let $b\in B$ be a neighbour of $w$, other than $v$, which lies on the boundary of $f$. Since $u$ and $b$ lie on the boundary of the same face, in different parts of the bipartition of $G$, they are adjacent by the maximality of $G$, contradicting the fact that the degree of $u$ is 1.
Best Answer
A formal proof has been produced. See https://arxiv.org/abs/2105.07161