3
$\begingroup$

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

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

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.

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

2 Answers 2

3
$\begingroup$

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

enter image description here

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Sep 24, 2022 at 13:12
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 24, 2022 at 13:17
  • $\begingroup$ +1. That's great. I see. $\endgroup$
    – licheng
    Sep 24, 2022 at 13:21
3
$\begingroup$

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]

enter image description here enter image description here enter image description here

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]
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Sep 25, 2022 at 2:24
  • $\begingroup$ Here, there is a similar discussion(cstheory.stackexchange.com/questions/27586/…). From some answers, orienting each edge would be helpful in identifying exterior faces. But I haven't seen the details of the implementation. $\endgroup$
    – licheng
    Sep 25, 2022 at 2:24
  • 1
    $\begingroup$ @licheng: I updated my answer with code that identify exterior face in general case. $\endgroup$ Sep 25, 2022 at 9:36

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.