For any planar quadrangulation $G$, is there a planar drawing of $G$ such that all faces are convex (or non-convex, resp.)?

Question

A simple planar graph $G$ is called a quadrangulation graph if $G$ has a planar drawing in which all faces are quadrangular faces.

A polygon is convex if all the interior angles are at most 180 degrees. A polygon is non-convex if one or more of the interior angles is more than 180 degrees.

A planar drawing is called convex planar drawing (non-convex planar drawing, resp.) if all of the faces of the drawing (including the outer face) have a convex boundary (non-convex boundary, resp.).

My questions are inspired by the recent question:

• Planar quadrangulations with only non-convex faces

In the answer, Brandon du Preez found some quadrangulations with minimum degee $2$ such that every face is non-convex. Misha Lavrov found that the minimum degee "2" is not necessary.

---

It is easy to see that the vertex connectivity of any quadrangulation graph is $2$ or $3$.

Tutte's embedding theorem says that every 3-connected planar graph have a convex (even strictly convex) planar drawing. So if a quadrangulation graph is 3-connected, of course it has a convex planar drawing. So here is an interesting question:

• does every 3-connected quadrangulation graph have a non-convex drawing?

What about the case where the vertex connectivity of quadrangulation graphs is not $3$? Two specific questions are as follows.

• does every quadrangulation graph with vertex connectivity $2$ have a convex planar drawing?
• does every quadrangulation graph with vertex connectivity $2$ have a non-convex planar drawing?

Answer 1

To find a non-convex embedding of any planar quadrangulation $G$, induct on the number of vertices. We prove that for any plane embedding of $G$, there is a plane embedding with the same face structure where all faces have a concave angle. (The base case is the $4$-cycle, which we can embed as any concave quadrilateral.)

The general strategy is to find a low-degree vertex to remove. With $n$ vertices, there are $n-2$ faces and $2n-4$ edges, for an average degree of $4 - \frac8n$, so we can find a vertex $v$ of degree $3$ or less. There are two cases depending on $\deg(v)$:

1. If $\deg(v)=2$ with neighbors $w_1, w_2$, then our plane embedding of $G$ gives us a plane embedding of $G-v$ (another quadrangulation!) where $w_1, w_2$ are opposite vertices on the same face. Find a non-convex embedding of $G-v$, then carefully put $v$ back.
2. If $\deg(v)=3$ with neighbors $w_1, w_2, w_3$, then our plane embedding of $G$ gives us a plane embedding of $G-v$ where $w_1, w_2, w_3$ are three non-consecutive vertices of a face of length $6$. Add an edge $e$ from $w_1$ to its opposite vertex on that face to get a quadrangulation. Find a non-convex embedding of this graph ($G-v+e$), then remove the edge we added and carefully put $v$ back.

Let me elaborate on the "carefully put $v$ back" steps, with some drawings.

---

In the degree-$2$ case, the non-convex plane embedding of $G-v$ has a face with four vertices $x_1, x_2, x_3, x_4$, where $x_1$ and $x_3$ are supposed to be adjacent to $v$. There are seemingly many cases, depending on whether the face is an interior or exterior face, and depending on which of $x_1, x_2, x_3, x_4$ gives us the non-convex angle.

However, we don't need to do casework; all cases can be solved by putting $v$ back sufficiently close to vertex $x_2$. First of all, this guarantees that edges $x_1v$ and $x_3v$ can be drawn as straight line segments (because they're very close to the straight line segments $x_1x_2$ and $x_3x_2$). Second, the two faces we get are

• $x_1vx_3x_4$, which is non-convex because it's very close to the former face $x_1x_2x_3x_4$, and
• $x_1x_2x_3v$, which is non-convex because we can make $\angle x_2x_1v$ and $\angle x_2x_3v$ arbitrarily small, and once $\angle x_2x_1v + \angle x_2x_3v < |\angle x_1x_2x_3 - 180^\circ|$, we know that either $\angle x_1 x_2 x_3$ or $\angle x_1 v x_3$ must exceed $180^\circ$.

---

In the degree-$3$ case, the non-convex embedding of $G-v+e$ has an embedding with two faces $x_1 x_2 x_3 x_4$ and $x_1 x_4 x_5 x_6$, where $e$ (the edge that doesn't exist in $G$) is $x_1 x_4$, and $v$ is supposed to be adjacent to $x_1, x_3, x_5$. Again, there are seemingly many cases for which face (if any) is an interior face, and which angles are concave. Here are a few:

However, once again, we can solve all the cases by placing $v$ sufficiently close to $x_4$. The three faces created are:

• $x_1 x_2 x_3 v$, which has a non-convex angle because it can be made arbitrarily close to the face $x_1 x_2 x_3 x_4$ in the non-convex embedding of $G-v+e$;
• $x_3 x_4 x_5 v$, which has a non-convex angle by the same argument as in the degree-$2$ case ($\angle v x_3 x_4$ and $\angle x_4 x_5 v$ can be made arbitrarily small);
• $x_5 x_6 x_1 v$, which has a non-convex angle because it can be made arbitrarily close to the face $x_5 x_6 x_1 x_4$ in the non-convex embedding of $G-v+e$.