On Thu, Oct 2, 2008 at 3:00 PM, David Gleich
Hi,
I'm concerned about the output I'm getting from the is_straight_line_drawing function in the Boost Graph library. My understanding was that it should report true when the graph and positions are a planar embedding (no edge crossings).
Based on this understanding, I thought the code listed at the end of the message should say that the drawing for a clique on 4 vertices, with positions on a square, is not planar (see the picture below). This arrangement has one edge crossing. The function outputs that the graph is a plane drawing.
Did I misunderstand what the is_straight_line_drawing function is supposed to do?
Thanks, David Gleich
<snip>
/* should be 0 / | \ 3--|--1 \ | / 2 which is not a plane drawing. */
<snip> Hi David, You're right - this looks like a bug in is_straight_line_drawing. The sweep of the plane isn't comparing the two perpendicular edges (0,2) and (1,3), which intersect. I'll look at the code a little more closely this weekend and see if I can't come up with a fix. Regards, Aaron