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

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:

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?
• As for the second question, I bet that $K_{2,n}$ does not have a convex planar drawing when $n$ is large enough. (Maybe even $K_{2,4}$ already does not.) Commented Aug 26, 2022 at 13:49
• @MishaLavrov Nice! The other two problems have also been solved. I consulted the paper: Di Battista, G., Frati, F., Patrignani, M. (2009). Non-convex Representations of Graphs. In: Tollis, I.G., Patrignani, M. (eds) Graph Drawing. GD 2008. Lecture Notes in Computer Science, vol 5417. Springer, Berlin, Heidelberg. doi.org/10.1007/978-3-642-00219-9_38. The authors showed that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are non-convex polygons. Commented Aug 27, 2022 at 11:05
• Aww, and here I was about to post my solution to the other two problems. I think I might write it up anyway, because the solution for quadrangulations is somewhat simpler than the general solution. Commented Aug 27, 2022 at 16:13

## 1 Answer

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