Could you please post a drawing? For me

it isn't clear what you're going to achieve.

Regards,

Joachim

I have attached a drawing.

Figures in attached drawing file shows the circular layout of the graph. Consider a graph with 4 vertices and 4 edges.

If we apply boost circle_graph_layout on this graph it gives layout as shown in figure (a) and so I would like to pass the vertex sequence 0,2,1,3 to boost circle_graph_layout function in order to get expected output shown in figure (b).

In figure (a), vertex sequence is 0,1,2,3. If we change the sequence to 0,2,1,3 the edge crossover is removed as shown in figure (b).

boost circle_graph_layout has following definition:

template

void circle_graph_layout(const VertexListGraph& g, PositionMap position,

Radius radius)

{..}

There is no room to pass vertex sequence in which we want to lay out the vertices.

So could you please help with some ways to achieve the expected layout?

Is there any other alternative to this?

I've got no experience with the boost library, but why not

arranging the layout by yourself? You have to find a

permutation such that intersections are minimized. No vector

arithmetic is necessary since in this special case there is

an easy characterization. If you walk around the circle,

beginning at a node with an edge, ending at its graph

neighbor, all edges of vertices between must have both

ends in the set of vertices you will encounter on the walk.

You have to minimize the sum of violations. Seems

like a kind of Travelling Salesman problem, but with only

few nodes Threshold Accepting or Simulated Annealing

should suffice.

Regards,

Joachim

Thank you Joachim for your answer. It will help to find the sequence of vertices which gives minimum edge crossovers. But the problem is plotting the vertices sequence in circular fashion using boost library. Actually I have to use boost for laying out graphs in my project. Boost has a function circle_graph_layout which takes graph and plot the vertices according to their vertex index (i.e. 0-1-2-3 likewise), but there is no straight forward way to provide the vertices sequence which I want to be plotted (e.g. 0-2-1-3 from my example) to this function.

I would like to know that how can we change the vertex order in a boost graph, or any alternative to pass vertex order to boost circle_graph_layout.

Regards,

Pratik

Bor Plestenjak's algorithm for drawing planar graphs is a well known algorithm for drawing circular layouts. It draws some of vertices as specified in input as outer cycle of a regular polygon and place all others into center of the polygon, then by applying that algo you can get a very pleasing and crossing free layout. I have worked on that and you can get that by an email.