A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) 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 on $V_1$, $V_2$.
Start with first $i$ vertices of $V$ in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
In iteration $i$, let our current chosen vertex set be $V_{i1}$
If $\exists x \in V_{i1}$ such that $d_{H}(x) \lt \frac12 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}$.
Similarly do for $ V_{i2}$. If $\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.
Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
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:
Could somebody help me analyze this algorithm?
Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?
2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?
