# Ordering vertices with minimum Edge Crossing in Circular Graphs

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


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.

-

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.

Other related works are:

-