Re: [Boost-users] [Graph] Issue with is_straight_line_drawing?

Subject: Re: [Boost-users] [Graph] Issue with is_straight_line_drawing?
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-10-03 09:08:34

On Thu, Oct 2, 2008 at 3:00 PM, David Gleich <dgleich_at_[hidden]> wrote:
> 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