Re: [boost] drawing planar graphs

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-04-10 08:43:27

On Thu, Apr 10, 2008 at 4:10 AM, Vicen <vgomez_at_[hidden]> wrote:
> Hi,
>
>  thanks Aaron. Another point: Is there any example to get a planar
>  drawing without making the graph maximal planar?
>
>  In the straight_line_drawing documentation this procedure is outlined. I
>  think it would be very useful to have an example in the documentation
>  which work for any planar graph without having to create explicitly the
>  triangulated one.

Hi Vicen,

The algorithm used to create a drawing of a planar graph
(Chrobak-Payne) requires that the graph be maximal planar. So there's
no way around this requirement if you want to use the function
chrobak_payne_straight_line_drawing, although you can ignore the edges
that you've added to make the graph maximal planar in the final
straight line drawing and get the same effect of a straight line
drawing of a non-maximal planar graph.

You have a good point - I'll include an example for the full procedure
of taking a graph and producing a straight line drawing for the next
release. In the meantime, there's a test that does exactly what you
describe that you can look at:
libs/graph/test/all_planar_input_files_test.cpp. This program iterates
through all graph files stored in a specified directory, and for each
one, either verifies that it's planar and creates a straight line
drawing of that graph (whether it's maximal planar or not) or verifies
that it isn't planar.

Regards,
Aaron