graph theoryplanar-graphs
A quadrangulation is a simple graph(map) where every face is quadrilateral.
It is not difficult to find that minimum degree of any quadrangulation is no more than $3$. Furthermore, connectivity of any quadrangulation is between $2$ and $3$.
I want to find some quadrangulations with connectivity $2$. It is easy to find when the minimum degree is $2$. For example: $K_{2,n-2}$.
However I have not found a quadrangulation with minimum degree $3$ and connectivity $2$.
Would separating $A$ into two nodes connected by one edge work? Also, the minimum degree of your graph is $2$ at each of the four corner nodes.
The graph with the largest minimum degree, lowest edge connectivity, and lowest vertex connectivity is formed by connecting two complete graphs with one singular edge like a bridge.
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)$:
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
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:
Best Answer
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
Some printed graph look as follows