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