This should be easy .... typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type>, LEN<position_type> > DG; typedef graph_traits<DG>::vertex_descriptor Vertex; typedef graph_traits<DG>::edge_descriptor Edge; ... Vertex b, d; ...populate b and .... bool bRet; Edge e; tie(e,bRet) = edge(b,d,*this); This earns me a lengthy error message from g++ (following). I notice that there is no function described for looking up an edge on an IncidenceGraph or an AdjacencyGraph ... hmm .... this puzzles me. What am I missing? Eric ../shuttle/trunk/DelaunayGraph.h:273: error: no matching function for call to ‘DelaunayGraph<int>::remove_edge(Edge&, DelaunayGraph<int>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:848: note: candidates are: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::edge_descriptor) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] /usr/include/boost/graph/detail/adjacency_list.hpp:859: note: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::out_edge_iterator) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] make: *** [MyDialog.o] Error 1