A procedure by induction to get maximum spanning bipartite graph from given graph $G$: 


Given a planar graph $G$. We need two disjoint sets $V_{1}$ and $V_{2}$. We define $V_{2} = V  \setminus  V_{1}$ where $V = V(G)$  
In the following $H$ is the bipartite subgraph with  $ V(H) =  V_{1} \sqcup V_{2} $ and 
$E(H) = K_{V_1,V_2} \cap E(G) $ where $K_{V_1,V_2}$ is the complete bipartite graph with $V_1,V_2$ 



1. Start with first i vertices of V in vertex set $V_{01} \subseteq V$ and then  $V_{02} =  V  \setminus  V_{01}$ 
2. In step i, let our current chosen vertex set be $V_{i1}$
3.  If $\exists x \in V_{i1}$ such that  $d_{H}(x) < \frac{1}{2} d_{G}(x)$ then consider the bipartite spanning graph $H'$ with 
$V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$\\ 
$E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. 
We are basically moving vertex x which satisfies above property from $V_{i1}$ to $V_{i2}$.
4. Similarly do for $ V_{i2}$. $\exists x \in V_{i2}$ such that  $d_{H}(x) < \frac{1}{2} d_{G}(x) $ Move vertex x to $V_{i1}$ .Go to step 2.
5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$. 


We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$ 

Analysis of this procedure: 
For each vertex in initial $V_{01}$ we do $(n-i)$ operations. Similarly for the other $(n-i)$ vertices in the other vertex set $V_{02}$ we do $i$ operations. We need to repeat this in the worst case i times. Hence upper bound is $O(n^3)$. So I am getting a polynomial time algorithm. What I am doing wrong. Is this not a NP problem. Could someone help me in analyzing this algorithm.