Is it possible to add edges to a graph while preserving the structure? This is similar to preserving structure while deleting a node, but that method is tailored for removing nodes and doesn't obviously help when adding edges.

Consider a triangle (cycle graph), where I want to think of the three vertices as "external" while adding an "internal" vertex between vertices 1 and 2:

start = CycleGraph[3, VertexLabels->Automatic];
badEnd = EdgeAdd[EdgeDelete[start, 1 <-> 2], {1 <-> internal, 2 <-> internal}];
(* I don't care where the new node is, just that it's somewhere "between" the 1 and 2 *)
(* Control the location via a and b *)
{a, b} = {0.35, 0.2};
vc =
 {internal -> (a GraphEmbedding[start][[1]] + b GraphEmbedding[start][[2]])}
 MapThread[#1 -> #2 &, {VertexList[start], GraphEmbedding[start]}]
goodEnd = Graph[badEnd,VertexCoordinates -> vc];

The badEnd Graph displays in a terrible way in this instance.

In contrast, goodEnd keeps the three original vertices, and internal is generally between vertices 1 and 2, and can be moved around by changing a and b.

I want a general way of implementing something like goodEnd. Ideally would be

internal -> Automatic

instead of

internal -> (a GraphEmbedding[start][[1]] + b GraphEmbedding[start][[2]]) 

in the vc list. I'm aware of Graph[badEnd, GraphLayout -> "SpringElectricalEmbedding"], (for example) but the graphs in my real examples do not behave nicely under these layouts.

  • $\begingroup$ I get the sense you're mostly looking for something built-in. In lieu of that, are you interested in some code to handle this? It mostly seems like (1) adding a new node to a graph with the previous nodes fixed, plus (2) making sure the new node is placed 'nicely' -- that is (2a) in the interior of the other nodes (which might be slightly nontrivial for Length@VertexList@start > 3) and (2b) that the new node is somehow visually nicely placed (e.g., avoiding any nearly-coinciding nearly-parallel edges). This is not completely trivial, but I'm guessing you've thought about this. $\endgroup$
    – jjc385
    Dec 16, 2017 at 11:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.