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

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?[", "KsIB?oE?K_]", "KsIb?oE?K_["};
s1 = ImportString[#, "Graph6"] & /@ s;
Module[{g1 = g, newgraph, p, addedge},  p = PlanarFaceList[g1];
addedge = {#[[1]] <-> #[[3]], #[[2]] <-> #[[4]]} & /@ p //
Flatten;
HighlightGraph[newgraph,
Style[ addedge, {{Dashed, Red, AbsoluteThickness[1]}}]]];
S2 = IGLayoutTutte /@ s1


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};
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.

• Take one of your graphs and do it manually to show us what exactly you want your graph to look like. Commented Sep 23, 2022 at 17:11

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


• Thank you for your help. I think your code needs more work. First of all, there is no guarantee that the quadrilateral is strictly convex when randomly generated. Secondly, your answer also raises the key question of how to ensure that the new edges added always fall outside the randomly generated quadrilateral and that they only cross once. Commented Sep 24, 2022 at 13:12
• First, I used SeedRandom to create an example. It is up to you to deliver convex quadrilateral. Second, as I already said, the parameter "lam" must be adjusted if the curve is not outside. Commented Sep 24, 2022 at 13:17
• +1. That's great. I see. Commented Sep 24, 2022 at 13:21

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?[", "KsIB?oE?K_]",
"KsIb?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;
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] /.
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;
"KsIb?oE?K_["};
`
• The way you identify the exterior faces seems to be by picking out the four vertices whose coordinates are $(-1, y), (1, y), (x,-1)$ and $(x,1)$, respectively. This is a special but interesting method. However, I would like to ask whether there is a general way to identify the exterior face of a planar embedding of a graph. Commented Sep 25, 2022 at 2:24