2
$\begingroup$

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?
$\endgroup$
3
  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Aug 26, 2022 at 13:49
  • $\begingroup$ @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. $\endgroup$
    – licheng
    Commented Aug 27, 2022 at 11:05
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 27, 2022 at 16:13

1 Answer 1

2
$\begingroup$

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:

enter image description here

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .