A simple graph $G$ is called maximal planar bipartite if it has the property: if we add an edge (without adding vertices) to $G$, we obtain a graph which is no longer planar, bipartite or simple.
See the following article for the above definition.
- [1] G. Ringel, Two trees in maximal planar bipartite graphs[J]. Journal of Graph Theory, 1993, 17(6): 755-758.
But Ringel was quick to assert that a maximal planar bipartite graph divides the plane into quadrangles only.
When maximal bipartite planar graphs are 2-connected, I see no problem. But if a maximal planar bipartite graph has some cut vertices, it seems incorrect. For example, for the stars (a star $S_k$ is the complete bipartite graph $K_{1,k} $), clearly they are maximal planar bipartite graphs. But they are not quadrangulations (a graph can be embedded in a surface such that every face is a quadrangle).
Furthermore, my question is whether all maximal planar bipartite graphs except stars are quadrangulations.
Some examples show that it seems right.
But how do we prove it rigorously?
PS (screenshot from Literature 1):
Yes, they are (and well spotted).
Here's an old proof I have typed up. I think you can shorten it substantially however! To do so, I'd directly consider the walk bounding a face. It consists of alternating black / white vertices. Try argue using maximality that the walk is either a 4-cycle, or a star.
Lemma 1: Every face of a 2-connected plane graph is bounded by a cycle. This is well known (see, for example, Diestel)
Theorem 1: Let $G$ be an mpb graph of minimum degree $\delta$ embedded in the plane. Then every face of $G$ is bounded by a 4-cycle if and only if $\delta \geq 2$.
Proof: Let $G = (V,E)$ be an mpb graph and consider an embedding of $G$ in the plane. If every face of $G$ is bounded by a 4-cycle, then clearly $\delta \geq 2$. Conversely, assume $\delta \geq 2$. As $G$ is bipartite, $V$ can be partitioned into two sets, $B$ and $W$, such that every edge of $G$ is incident with one vertex of $B$ and one vertex of $W$.
First, we show that $G$ is 2-connected: Assume to the contrary, and without loss of generality, that $b_1\in B$ is a cut-vertex. Let $w_1, w_2$ be vertices of different components of $G-b_1$ such that $w_1, b_1, w_2$ are consecutive vertices of the walk bounding some face $f$ of $G$. As $w_1, w_2$ are adjacent to $b_1\in B$, it must be that $w_1, w_2 \in W$. Since the minimum degree of $G$ is at least 2, $w_2$ has a neighbour $b_2\in B$ such that $w_2, b_2$ are consecutive vertices of the walk bounding $f$. Since $b_2$ and $w_1$ are in different parts of the bipartition of $G$, and are both on the boundary of $f$, the maximality of $G$ implies that $w_1b_2 \in E$. Thus, $w_1, w_2$ lie in the same component of $G-b_1$, a contradiction. Hence $G$ is 2-connected.
We now show that every face of $G$ is a 4-cycle: Since $G$ is 2-connected and bipartite, by Lemma 1, every face is bounded by an even cycle. Thus it suffices to prove that every face of $G$ is bounded by a cycle of length less than 6. Assume, to the contrary, that some face $f$ of $G$ is bounded a cycle $C$ of length $k\geq 6$ and, without loss of generality, that $f$ is in the interior of $C$. Let $b_1, w_1, b_2, w_2, b_3, w_3$ be six consecutive vertices of $C$ with $b_1, b_2, b_3 \in B$ and $w_1, w_2, w_3 \in W$. As $b_1$ and $w_2$ lie on the same face and are in different parts of the bipartition of $G$, the maximality of $G$ implies that $b_1w_2 \in E$. Since the interior of $C$ is a face, $b_1w_2$ must lie in the exterior of $C$. Similarly to $b_1w_2$, the maximality of $G$ necessitates that $w_1b_3\in E$. If $w_1b_3$ lies inside $C$, it subdivides $f$, contradicting that $f$ is a face. If $w_1b_3$ lies outside $C$, it crosses $b_1w_2$, contradicting the planarity of $G$.
Theorem 2: If $G$ is an mpb graph of minimum degree one, then $G$ is a star.
Proof: Let $G = (V,E)$ be an mpb graph with partite sets $B$, $W$, and consider an embedding of $G$ in the plane. Without loss of generality, $v\in B$ is the neighbour of a vertex of degree 1. We claim that every neighbour of $v$ has degree 1. Assume to the contrary that $v$ has a neighbour of degree greater than 1. We can find neighbours $u,w$ of $v$ with $\text{deg}(u) = 1$ and $\text{deg}(w) \geq 2$ such that $u,v,w$ lie on the same face, $f$, of $G$. Let $b\in B$ be a neighbour of $w$, other than $v$, which lies on the boundary of $f$. Since $u$ and $b$ lie on the boundary of the same face, in different parts of the bipartition of $G$, they are adjacent by the maximality of $G$, contradicting the fact that the degree of $u$ is 1.