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

graph theoryplanar-graphs

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?

Best 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)$:

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

Related Solutions

Construct a quadrangulation with connectivity 2 and minimum degree 3

You can use SageMath with plantri, a tool written by Brinkmann et. al to generate all quadrangulations up to isomorphism with the desired properties as follows

for n in range(1, 15):
    gen = graphs.quadrangulations(n, minimum_degree=3, minimum_connectivity=2)
    for g in gen:
        if g.vertex_connectivity() == 2:
            g.show()

Some printed graph look as follows

Analogous formula for finding “non-planar graphs” using defined faces instead of edges in $\Bbb R^3$

I don't know an efficient algorithm in general, but your final paragraph just says that you are looking for a simple example of something non-embeddable. For this, I would use a triangulation of the projective plane.

You can achieve this with just $6$ vertices, which I'll call $\{ a,b,c,d,e,f \}$. The edges are the complete graph $K_6$ and the triangles are

abf, bcf, cdf, def, eaf, abd, bce, cda, deb, eac .

I found a picture of this simplicial complex here.

I computed this by taking the $12$ vertices of an icosahedron (which is a triangulation of the sphere $S^2$) and labeling antipodal vertices with the same number. The $20$ triangles in the icosahedron get $10$ distinct labels, which are the labels listed above. So we get a triangulation of $S^2 / \langle \pm 1 \rangle$, which is to say, a triangulation of $\mathbb{RP}^2$.

If you aren't comfortable with projective planes and quotient spaces, you can see the structure of this example by looking at the first 5 triangles I've listed and the last 5. The first 5 triangles form a pentagonal disc, with boundary $abcde$ and $f$ in the center. The other 5 form a Mobius strip, with boundary $abcde$. So the point is that you can't sew the boundary of a disc to the boundary of a Mobius strip.

$6$ vertices are optimal. If we have any simplicial complex with $5$ (or fewer vertices), we can send the $4$ of the points to the vertices of a tetrahedron and the last point to the interior, join all edges with straight line segments and fill all faces with triangles, and this will have no self intersections.

I also found this old question, which says that the minimal triangulation of a Klein bottle has $8$ vertices.

Regarding algorithms: You could ask about linear embeddings, meaning that all edges must be sent to line segments and all faces to triangles, or you could ask about continuous embeddings. (There are also things like "piecewise linear", "piecewise smooth" or "smooth", but I think those should all be equivalent to continuous.)

For linear embeddings, this is a matter of solving finitely many polynomial inequalities in finitely many variables: Write the coordinates of each vertex as $v_i:=(x_i, y_i, z_i)$ and then write down an inequality saying that faces which are supposed to be disjoint don't cross. I think it should be enough to impose, for every face $(v_1, v_2, v_3)$, and every edge $(v_4, v_5)$, that the line segment doesn't cross the interior of the triangle. To do this, solve the linear equations $$\begin{bmatrix} x_1&x_2&x_3&-x_4&-x_5 \\ y_1&y_2&y_3&-y_4&-y_5 \\ z_1&z_2&z_3&-z_4&-z_5 \\ 1&1&1 & 0&0 \\ 0&0&0&1&1 \\ \end{bmatrix} \begin{bmatrix} p_1\\p_2\\p_3\\p_4\\p_5 \end{bmatrix} = \begin{bmatrix} 0\\0\\0\\1\\1 \end{bmatrix}$$ to find $(p_1, p_2, p_3, p_4, p_5)$ with $p_1 v_1 + p_2 v_2 + p_3 v_3 = p_4 v_4 + p_5 v_5$, and $p_1+p_2+p_3 = p_4+p_5 = 1$; then impose that the $p_i$ are not all positive. (You'll also want to impose that $v_i \neq v_j$ and that $(v_i, v_j, v_k)$ are not collinear for any face $(v_i, v_j, v_k)$.) You can write down explicit formulas for the $p$'s in terms of the $x$'s, $y$'s and $z$'s using Cramer's rule. By Tarski's theorem, there is an algorithm that decides whether any collection of polynomial inequalities has a real solution. I was not able to find any literature about the complexity of this case.
Switching to continuous embeddings, the main result of "Embeddability in the 3-sphere is decidable" is that this is decidable and the main result of "Embeddability in $\mathbb{R}^3$ is NP-hard" is that it is NP-hard. I couldn't find any references saying whether or not the problem is in NP. The first paper also shows that continuous and PL-embeddability are equivalent. Disclaimer: I haven't read either paper.

Best Answer

Related Solutions

Construct a quadrangulation with connectivity 2 and minimum degree 3

Analogous formula for finding “non-planar graphs” using defined faces instead of edges in $\Bbb R^3$

Related Question