How to draw intelligently a pair of crossing edges inside the exterior face of a convex quadrilateral?

Question

First we draw a 4-cycle $C_4$ on the plane such that its edges form a convex quadrilateral $f$. I'd like to draw a pair of new crossing edges inside the exterior face of $f$. (Notice that the two new crossing edges cross exactly once, and they don't cross any boundaries of $f$.) Clearly, whatever the shape of the quadrilateral, at least one of these two new edges must be curved.

If the shape of the quadrilateral is fixed (i.e. , the coordinates of vertices on the boundary of $f$ are given), then we can choose to add two new edges manually.

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 1, 4 <-> 2, 1 <-> 3}, 
  EdgeShapeFunction -> {1 <-> 3 -> {"CurvedEdge", "Curvature" -> 3}, 
    2 <-> 4 -> {"CurvedEdge", "Curvature" -> -3}}, 
  VertexCoordinates -> {{0, 0}, {1, 0}, {1, -1}, {0, -1}}]

If the shape of the quadrilateral is random, (i.e., the coordinates of the quadrilateral are chosen randomly), how do we add the two new edges well?

---

This question arises from a drawing problem involving graphs. I got some 3-connected quadrangulation graphs. I want to add a pair of crossing edges to every face of these planar graphs at once. For these planar graphs, I first chose the Tutte spring embedding. So the external faces are bounded by convex polygons. But the coordinates of the external faces of these embeddings are random.

<< IGraphM`;
s = {"KsTAB?oBGL?[", "Ks`IB?oE?K_]", "Ks`Ib?oE?K_["};
s1 = ImportString[#, "Graph6"] & /@ s;
addCrossingEdgesToFaces[g_] := 
  Module[{g1 = g, newgraph, p, addedge},  p = PlanarFaceList[g1];
   addedge = {#[[1]] <-> #[[3]], #[[2]] <-> #[[4]]} & /@ p // 
     Flatten;
   newgraph = EdgeAdd[g1, addedge]; 
   HighlightGraph[newgraph, 
    Style[ addedge, {{Dashed, Red, AbsoluteThickness[1]}}]]];
S2 = IGLayoutTutte /@ s1
addCrossingEdgesToFaces /@ S2

For beauty and clarity, the pair of crossing edges that should be on the exterior face of each graph above need to be adjusted.

---

In response to Azerbajdzan's doubts, I gave a more detailed manual solution.

Step 1. We need to identify the exterior face of the plane embedding of a graph g. I don't know if there's a code to seek the exterior face. (perhaps as a new problem), but for the specific graph, we can see from the label of the drawn graph.

g = Graph[ImportString["KsTAB?oBGL?[", "Graph6"]];
gtest = Graph[ImportString["KsTAB?oBGL?[", "Graph6"], 
   VertexLabels -> Placed[Automatic, Center], VertexSize -> 0.8, 
   GraphLayout -> "TutteEmbedding"];
coords = GraphEmbedding[gtest];

So $1-2-3-8-1$ is the exterior face of graph g.

Step 2. add two new crossing edges in the exterior face $1-2-3-8-1$.

addedge = {1 <-> 8, 2 <-> 3};
g1 = Graph[EdgeAdd[g, addedge], 
   VertexCoordinates -> coords, 
   EdgeShapeFunction -> {1 <-> 8 -> {"CurvedEdge", "Curvature" -> 3}, 
     2 <-> 3 -> {"CurvedEdge", "Curvature" -> -3}}];
HighlightGraph[g1, Style[ addedge, {{Dashed, Red, AbsoluteThickness[1]}}]]

The remaining faces are added with a pair of crossing edges. As they are guaranteed to be straight lines (since each face is a strictly convex polygon). It's easy. So let's skip that.

Answer 1

We may take vertices 1,2,3 and 2,3,4 as control points of a Bezier curve. Toward this aim, we extend the middle point away from the opposite point by "lam" to ensure that the curve lies in the outside of the quadrilateral. Depending on the data, the parameter "lam" must eventually be increased:

We first create some convex quadrilateral:

SeedRandom[8];
ed = Partition[t = RandomReal[{-1, 1}, {4, 2}], 2, 1, {1, 1}, t];

And then we create the Bezier curves:

lam = 2;
curves = {BSplineCurve[
   ed[[2 ;; 4, 1]] + {{0, 0}, lam (ed[[3, 1]] - ed[[1, 1]]), {0, 0}}],
   BSplineCurve[
   ed[[;; 3, 1]] + {{0, 0}, lam (ed[[2, 1]] - ed[[4, 1]]), {0, 0}}]}
Graphics[{curves, Green, Line[ed]}]

Answer 2

This seems to work for the given three graphs. Change integer 1 in the first line of code to 1, 2 or 3 to choose one of the three graphs.

g = ImportString[{"KsTAB?oBGL?[", "Ks`IB?oE?K_]", 
     "Ks`Ib?oE?K_["}[[1]], "Graph6"];
AnnotationValue[g, GraphLayout] = "TutteEmbedding";
AnnotationValue[g, VertexCoordinates] = GraphEmbedding[g];
AnnotationValue[g, PlotRange] = 2;
sp = Select[GraphEmbedding[g], 
   Length[# \[Intersection] {1., -1.}] > 0 &];
out = Position[GraphEmbedding[g], #] & /@ 
    sp[[FindShortestTour[sp][[2, 1 ;; 4]]]] // Flatten;
ng = addCrossingEdgesToFaces@g;
out2 = Alternatives @@ ({out[[1]] \[UndirectedEdge] out[[3]], 
      out[[2]] \[UndirectedEdge] out[[4]], 
      out[[3]] \[UndirectedEdge] out[[1]], 
      out[[4]] \[UndirectedEdge] out[[2]]} \[Intersection] 
     EdgeList[ng]);
AnnotationValue[ng, 
   EdgeShapeFunction] = {out2 -> {"CurvedEdge", "Curvature" -> 3}};
ng
Clear[g, sp, out, out2, ng]

Update:

The following code determines exterior face in all circumstances.

addCrossingEdgesToFaces2[g_] := 
 Module[{g1 = g, newgraph, p = PlanarFaceList[g], emb, addedge, 
   center, ext},
  AnnotationValue[g1, GraphLayout] = "TutteEmbedding";
  emb = GraphEmbedding[g1];
  AnnotationValue[g1, VertexCoordinates] = emb;
  AnnotationValue[g1, PlotRange] = 2;
  center = List @@ BoundingRegion[emb] // Mean;
  ext = Take[
     SortBy[GraphEmbedding[g1], 
      EuclideanDistance[center, #] &], -4] /. 
    Thread[emb -> VertexList[g1]];
  ext = Select[p, Length[ext ⋂ #] == 4 &] // First;
  ext = Alternatives @@ ({#[[1]] \[UndirectedEdge] #[[3]], #[[2]] \
\[UndirectedEdge] #[[4]]} &@ext);
  addedge = {#[[1]] \[UndirectedEdge] #[[3]], #[[2]] \
\[UndirectedEdge] #[[4]]} & /@ p // Flatten;
  newgraph = EdgeAdd[g1, addedge];
  AnnotationValue[newgraph, 
    EdgeShapeFunction] = {ext -> {"CurvedEdge", "Curvature" -> 3}};
  HighlightGraph[newgraph, 
   Style[addedge, {{Dashed, Red, AbsoluteThickness[1]}}]]]

g = ImportString[#, "Graph6"] & /@ {"KsTAB?oBGL?[", "Ks`IB?oE?K_]", 
    "Ks`Ib?oE?K_["};
addCrossingEdgesToFaces2 /@ g // Column
Clear[g]