# On Bipartite planar graph (again)

Given $n$ vertices of color $1$ and m vertices of color $2$, what is the maximal number of edges that can join them on the constraints - $(a)$ no edge joins has the same color ends and $(b)$ no two edges intersect when drawn on a plane (a planar graph)?

Also given such $n$, $m$ how many such graphs can be generated so that no vertex is isolated and how many maximal non-equivalent maximal graphs are possible?

Are these standard questions that have been studied anywhere?

$n = m$ is the case I am looking for a lead.

• Presumably "again" refers to your earlier question: cstheory.stackexchange.com/questions/5331/… – Dave Clarke Mar 10 '11 at 18:41
• Yes. But the older one asks for explicit construction. This one seems outwardly simpler!! – T.... Mar 10 '11 at 18:42
• Next time, please provide the necessary link(s) by yourself rather than relying on the moderators doing the task for you. – Tsuyoshi Ito Mar 10 '11 at 20:45

## 1 Answer

If $\min(m,n)=1$, the maximum number of edges in a planar bipartite graph with $m$ vertices on one side of the bipartition and $n$ on the other side is $m+n-1$ (just connect them in a star). Otherwise, the maximum number is $2(m+n)-4$.

The upper bound (any bipartite planar graph with $V$ vertices has at most $2V-4$ edges) follows by combining Euler's formula $V-E+F=2$ with the observation that all faces have at least four edges, and each edge belongs to at most two faces, so $E\ge 2F$. Use this inequality to eliminate $F$ from Euler's formula and you get $E\le 2V-4$.

For the lower bound, choose two vertices from the side with $m$ vertices and form a complete bipartite graph $K_{2,n}$ with $2n$ edges. Then, choose one of the quadrilateral faces of this graph and place the remaining $m-2$ vertices into it, connecting each one to both of the vertices of the other color within the same face, adding $2(m-2)$ more edges.

As for the number of distinct maximal planar bipartite graphs on this many vertices, I don't know, but it's certainly some kind of exponential.