Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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*)
Needs["Combinatorica`"];
sortedVertices = 
  Sort[Union[
    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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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:

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.