Weighted and sorted Mathematica circular graphs are shown below. My question is how to reorder the vertices in such a way that they have minimum cuts (intersection of edges) while keeping the circular graph in shape.

Some useful links to GraphPlot, circular graph and EdgeRenderingFunction for edge thickness from Mathematica.StackExchange and StackOverflow:

Mathematica code:

(*vertex shape function with labels*)
options = 
  Sequence[Method -> "CircularEmbedding", VertexLabeling -> True, 
   EdgeLabeling -> False,
   EdgeRenderingFunction -> ({Text[Style[#3, 15], Mean[#1]],
       Blue, AbsoluteThickness[0.8 + #3/5],
       Arrowheads[0.02 + #3/170],
       Arrow[#1, 0.075]} &), ImageSize -> 200];

Default Mathematica circular graph arranges vertices differently.

(*default mathematica circular graph*)
connections = {{1 -> 5, 1}, {4 -> 3, 3.6}, {6 -> 8, 1}, {2 -> 4, 
    2}, {2 -> 5, 2.5}, {5 -> 4, 0.9}, {7 -> 8, 2}, {3 -> 8, 
    1}, {8 -> 2, 1}};
gp1 = GraphPlot[connections, options];

So, we need to sort circular graph vertices to start calculating minumum cut (intersecting edges).

(*sorted mathematica circular graph*)
sortedVertices = 
    Flatten[{connections[[All, 1, 1]], connections[[All, 1, 2]]}]]];
sortedConnections = Table[
   sortedVertices[[i]] -> 
    Partition[Flatten[CircularEmbedding[Length[sortedVertices]]], 2][[i]],
   {i, Length[sortedVertices]}];
gp2 = GraphPlot[connections, options, 
   VertexCoordinateRules -> sortedConnections];
(*show two graphs*)
Row[{gp1, gp2}]

Mathematica graphics

The question is how the above code can be rearranged in such a way that GraphPlot has minimum cuts (intersection of edges) while keeping the circular graph in shape. The vertex points order may be changed but not the number of connections or directions.


1 Answer 1


After some investigation I come up with some below listed links that might be useful.

According to Michael Baur and Ulrik Brandes in paper 'Crossing Reduction in Circular Layouts':

Circular crossing minimization is NP-hard problem. On the other hand, a graph has a circular layout with no crossings, if and only if it is outerplanar. A linear time recognition algorithm for outerplanar graphs can easily extended to yield a crossing free circular layout.Since, in particular, trees have circular layouts with no crossings, it is possible to consider the biconnected components of a graph separately, and insert their circular layouts into a crossing free layout of the block-cutpoint-tree without producing additional crossings. See figure below for an illustration.

Mathematica graphics

Other related works are:


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.