Re: [boost] [Boost Vault] bug in straight_line_drawing

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-05-09 06:45:48

On 5/8/07, Dmitry Kamenetsky <dimkadimon_at_[hidden]> 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