On Thu, Apr 10, 2008 at 4:10 AM, Vicen <vgomez@iua.upf.edu> 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