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:
> 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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk