What is the maximum number of edges in a planar bipartite graph that has n vertices from each side?

Question

What is the maximum number of edges in a planar bipartite graph of order 2n that has n vertices from each side?

Answer 1

In every planar graph we have (Euler's formula):

$$V - E + F = 2$$

Where $V$, $E$, $F$ is the number of vertices, edges and faces respectively. Since the bipartite graph has no odd length cycles, the smallest cycle (and thus face) has $4$ edges. The sum of numbers of edges of each face equals twice the number of edges, so:

$$4F \le 2E$$

Which in conclusion with previous equality yields:

$$E \le 2V - 4$$

And in case of a bipartite graph having $n$ vertices on each side we have:

$$E \le 4n - 4$$

This can be achieved by an easy construction - picture $n$ vertices in a row numbered $1a$, $2a$, ... $na$ from one set and the other (call them $1b$, $2b$, ..., $nb$) directly below them (like in the grid). Then connect $1a$ to $1b$, $2a$ to $2b$ and so on with straight lines ($n$ edges), then connect $1b$ to $2a$, $2b$ to $3a$ and so on, again with straight lines ($n - 1$ edges) creating a "zigzag" pattern. Finally, connect $1a$ to all vertices on the other side by curved edges over of the grid ($n - 1$ edges because $1a$ and $1b$ are already connected) and connect $nb$ to all vertices on the other side by curved edges under the grid ($n - 2$ edges because $nb$ is already connected with $na$ and $1a$).