1
$\begingroup$

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.

![enter image description here

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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}]

enter image description here

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Dec 24, 2021 at 14:01
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Dec 24, 2021 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.