Hi, I can't figure out if it is possible (and if it is, how) to assign coordinates to graph vertices on planar graphs. I've tried setting the property vertex_index_t to std::pair<int, int> but it doesn't seem to work (make_maximal_planar doesn't use them for example). I'm trying to represent a 2D terrain via a triangular mesh. So far it is easy : I add all the points of the mesh as vertices and create the appropriated edges. But now I'm trying to make this graph evolve, which means adding new vertices (at some precise coordinates) and having them automagically linked to all other vertices possible while keeping the graph planar. This is what I do for now but that doesn't work (full source code is attached) : ------------------ typedef adjacency_list< vecS, vecS, undirectedS, property< vertex_index_t, std::pair<int, int> >, property<edge_index_t, int> > graph_t; typedef graph_traits<graph_t>::edge_descriptor edge_t; typedef graph_traits<graph_t>::vertex_descriptor vertex_t; // Create the graph graph_t g; // Add the three vertices of a triangle add_vertex(std::make_pair(0, 0), g); add_vertex(std::make_pair(10, 0), g); add_vertex(std::make_pair(5, 10), g); // Create the three edges add_edge(0, 1, g); add_edge(0, 2, g); add_edge(1, 2, g); // Add some random points add_vertex(std::make_pair(5, 5), g); add_vertex(std::make_pair(0, 5), g); // The goal is now to make g planar w.r.t. the coordinates // 1- Either make_connected or add at least one edge to make the graph // connected // 2- make_biconnected_planar // 3- make_maximal_planar ------------------ The input graph is (using boost::print_graph) : 0 <--> 1 2 1 <--> 0 2 2 <--> 0 1 3 <--> 4 <--> The output graph is : 0 <--> 1 2 3 4 1 <--> 0 2 3 2 <--> 0 1 3 4 3 <--> 2 4 0 1 4 <--> 3 2 0 It isn't palanar w.r.t. the given coordinates because 3 can't be connected with 4 without crossing one of the edges of the triangle (3 is supposed to be inside the triangle whereas 4 is outside). I suppose that either I'm doing something wrong or that it might not be possible to use the library this way. Any help appreciated, Thanks ! -- Maxime