Maximal planar subgraph of $K_{n,n}$

Question

I was thinking about the following problem... planer subgraph of k4,4.

I understand the main argument that a bipartite (planar) graph has no odd cycles, and hence every cycle has length at least 4, and applying Euler's characteristic formulae, $v-e+f=2$, we have $f\geq4e$ and hence we can say that $e\leq 2v-4$.

Specifically, I have the following question:

1. Does the maximal planar subgraph of $K_{n,n}$ always have $e =4n − 4$ and $f= 2n − 2$?

   • I think Euler's characteristic formulae only gives an upper bound, and does not necessarily ensure equality will occur. However, while reading the following, https://core.ac.uk/download/pdf/46175385.pdf, in the second paragraph, it mentioned equality of the above, saying it's "well-known".

   • I might be mistaken, but I thought equality can only be proven if a drawing can be provided. Perhaps we can always form a $4-$cycle that links the vertices together since we started from a complete bipartite graph. Or perhaps I misunderstood Euler's characteristic formulae.

2. Is there a nice construction of that maximal planar subgraph? or at least a way to inductively draw it?

   • For $n=4$, the drawing is obvious. In the pdf linked above, they have a drawing for $n=8$ and $9$ in page 3.

Answer 1

You can always triangulate a planar graph, adding edges until all faces are triangles; so $e=3v-6$ is tight for maximal planar graphs.

Similarly, we can start with a $2n$-cycle (which is a planar subgraph of $K_{n,n}$) and "quadrangulate it". As long as there is a face with at least $6$ edges, you can add an edge inside that face, dividing it into two faces of smaller even length. Eventually we will end up with only faces of length $4$; at this point, $e = 2f$, which leads to $e = 2v-4 = 4n-4$ and $f = v-2 = 2n-2$.

You might sometimes have to worry about adding an edge which already exists, but is drawn outside that face. But there are many possible edges we can add, not all of which can have this problem. In particular: if $v_1, v_2, v_3, v_4, v_5, v_6$ are six consecutive vertices on the boundary of a face, then $v_1 v_4$ and $v_2v_5$ are both edges that respect the bipartition, and can't simultaneously be drawn outside the face (they'd cross).

There are also some constructions that are nice. Here are two, one for odd and one for even $n$. (I've drawn them for $n=10$ and $n=11$, but they generalize easily.)