<p>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$.</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-10T19:13:05.867Z
2011-04-05T10:11:44.967Z
2011-04-05T10:11:44.967Z
David Eppstein
<p>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)?</p>

<p>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?</p>

<p>Are these standard questions that have been studied anywhere?</p>

<p>$n = m$ is the case I am looking for a lead.</p>

CC BY-SA 2.5
2011-03-10T18:41:29.337Z
Presumably "again" refers to your earlier question: http://cstheory.stackexchange.com/questions/5331/construction-of-graph-embeddings-with-non-intersecting-edges
Dave Clarke
CC BY-SA 2.5
2011-03-10T18:42:26.907Z
Yes. But the older one asks for explicit construction. This one seems outwardly simpler!!
Turbo
CC BY-SA 2.5
2011-03-10T20:45:09.247Z
Next time, please provide the necessary link(s) by yourself rather than relying on the moderators doing the task for you.
Tsuyoshi Ito
<graph-theory><co.combinatorics>
On Bipartite planar graph (again)
Turbo
# On Bipartite planar graph (again)

(Asked by: username_0 on 2011-03-10)

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.

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_1**: Presumably "again" refers to your earlier question: http://cstheory.stackexchange.com/questions/5331/construction-of-graph-embeddings-with-non-intersecting-edges  
> **username_0**: Yes. But the older one asks for explicit construction. This one seems outwardly simpler!!  
> **username_2**: Next time, please provide the necessary link(s) by yourself rather than relying on the moderators doing the task for you.  

---

## 1 answers

### Answer by username_3 on 2011-03-10. Score: 15 | Accepted 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.


---

