On 5/8/07, Dmitry Kamenetsky <dimkadimon@mail.ru> wrote:

Hello,

I have tried to use straight_line_drawing.cpp that comes with Boost Vault. It works perfectly on the 7-node example provided. However, it breaks down when I use my own graphs.

It places nodes on top of each other when I do the following graph:

graph g(6); add_edge(0,1,g); add_edge(0,2,g); add_edge(0,3,g); add_edge(1,2,g); add_edge(1,3,g); add_edge(1,4,g); add_edge(1,5,g);

the output given is:

0 -> (0, 0) 1 -> (2, 0) 2 -> (0, 0) 3 -> (1, 1) 4 -> (0, 0) 5 -> (0, 0)

Nodes 0, 2, 4 and 5 occupy the same location, even though the graph is planar, simple and connected.

Furthermore, it gives me segmentation fault when I do the following K(3,3):

graph g(6); add_edge(0,1,g); add_edge(0,2,g); add_edge(0,3,g); add_edge(1,2,g); add_edge(1,3,g); add_edge(1,4,g); add_edge(1,5,g); add_edge(2,3,g); add_edge(3,4,g); add_edge(3,5,g); add_edge(4,5,g);

Hi Dmitry, The input to the straight line drawing function has to be a maximal planar graph. The first graph you mention is planar, but not maximal planar. The second graph is not planar and therefore can't be drawn with a planar straight line drawing. In the first case, there are two functions provided along with the other planar graph tools that can help: make_biconnected_planar and make_maximal_planar. There's a file called make_maximal_planar.cpp in the examples subdirectory of the planar_graphs.zip file that shows how to use these two functions correctly to create a maximal planar graph from an arbitrary connected graph. Since the edge set of your original graph is a proper subset of edges in the maximal planar graph, you can use the straight line drawing of the maximal planar graph to get a straight line drawing of the original graph. Regards, Aaron