# How to define some special planar quadrangulations?

I'm going to define some special planar quadrangulations:

Let $$H_0$$ be the $$4$$-cycle $${v_0v_1v_2v_3v_0}$$, let $$\phi_0$$ be a planar drawing of $$H_0$$, and let $$F^0_1$$ and $$F^0_2$$ be the faces of $$\phi_0$$. For each positive integer $$i$$, let $$H_i$$ be obtained from $$H_{i-1}$$ by adding a new vertex $$v_{i+3}$$ adjacent to $$v_{i+2}$$ and the non-neighbour of $$v_{i+2}$$ in the boundary of $$F^{i-1}_2$$ and let $$\phi_i$$ extend $$\phi_{i-1}$$ to a drawing of $$H_i$$ by drawing the new vertices and edges inside $$F^{i-1}_2$$. Let $${F^i_1 := F^{i-1}_1}$$ and let $$F^i_2$$ be a outer face of $$\phi_i$$ whose boundary contains $$v_{i+3}$$.

For example, we difine some above graphs with $$7$$ vertices as follows. Note that the process of construction relies heavily on plane drawing. There are two ways to connect new vertex and $$v_{i+2}$$ on the outer face of $$H_{i-1}$$ in every step. Then the resulting graphs may not be unique. But it doesn't matter to me. I just need to get one of them.

Mathematica 13.0 introduces a new function PlanarFaceList[g] which gives the list of faces of the planar graph g.

g = PlanarGraph[CycleGraph[4], VertexLabels -> Automatic];
g1 = EdgeAdd[g, {5 <-> 4, 5 <-> 2}];
PlanarFaceList[g1]
EdgeAdd[g1, {6 <-> 5, 6 <-> 1}]


The first problem I encountered was how to find the outer face containing $$v_{i+3}$$ and then add a new vertex in outer face and add two edges efficiently. We need to make sure that the new vertex fall on the outer face of the old graph to continue the next process.

The codes for adding vertices and edges above is all artificial observation, which is very bad for constructing large graphs.

## 1 Answer

In PlanarFaceList, the outer face is the one with a negative orientation. First define the function to find orientation of faces:

pOrientation[pts_] :=
With[{p = First[Ordering[pts]]},
NegativelyOrientedPoints[
pts[[Mod[{p - 1, p, p + 1}, Length[pts], 1]]]]]


and define function to add edges based on this:

addEdges[g_] :=
Block[{v, gg, coords, f, outer, p},
v = VertexCount[g];
gg = Graph[g, GraphLayout -> "PlanarEmbedding"];
coords = GraphEmbedding[gg];
f = PlanarFaceList[gg];
outer = SelectFirst[f, pOrientation[coords[[VertexIndex[gg, #]]]] &];
p = SelectFirst[outer, v == # &];
EdgeAdd[gg, UndirectedEdge[v + 1, #] & /@ outer[[Mod[{p, p + 2}, Length[outer], 1]]]]
]


For example,

Table[Nest[addEdges, g, i], {i, 3}]


• Thank you for your help. I am curious that you don't seem to have fixed the coordinates of the new vertex added at each step, but its position is very regular. It's amazing. Dec 24, 2021 at 14:01
• I am very worried that this function of addEdges: gg = Graph[g, GraphLayout -> "PlanarEmbedding"]; if mma will automatically change the vertex position of its plane embedding, the program will be very unstable. Dec 24, 2021 at 14:07