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 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map.hpp> #include <vector> #include <boost/graph/is_straight_line_drawing.hpp> using namespace boost; //a class to hold the coordinates of the straight line embedding struct coord_t { std::size_t x; std::size_t y; }; int main(int argc, char** argv) { typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_index_t, int> > graph; graph g(4); // make the clique on 4 vertices add_edge(0,1,g); add_edge(0,2,g); add_edge(0,3,g); add_edge(1,2,g); add_edge(1,3,g); add_edge(2,3,g); //Set up a property map to hold the mapping from vertices to coord_t's typedef std::vector< coord_t > straight_line_drawing_storage_t; typedef boost::iterator_property_map < straight_line_drawing_storage_t::iterator, property_map<graph, vertex_index_t>::type

straight_line_drawing_t; straight_line_drawing_storage_t straight_line_drawing_storage (num_vertices(g)); straight_line_drawing_t straight_line_drawing (straight_line_drawing_storage.begin(), get(vertex_index,g) ); /* should be 0 / | \ 3--|--1 \ | / 2 which is not a plane drawing. */ straight_line_drawing[0].x = 1; straight_line_drawing[0].y = 2; straight_line_drawing[1].x = 2; straight_line_drawing[1].y = 1; straight_line_drawing[2].x = 1; straight_line_drawing[2].y = 0; straight_line_drawing[3].x = 0; straight_line_drawing[3].y = 1; if (is_straight_line_drawing(g, straight_line_drawing)) std::cout << "Is a plane drawing." << std::endl; else std::cout << "Is not a plane drawing." << std::endl; return 0; } /* Compiling and example $ g++ -v Using built-in specs. Target: x86_64-linux-gnu Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.2.3 (Ubuntu 4.2.3-2ubuntu7) $g++ is_straight_line_drawing.cpp -I/home/dgleich/dev/lib/boost_1_36_0/ $./a.out Is a plane drawing. Should be Is not a plane drawing. */