As these graphs are always embedded, that is as there is a circular order of edges we introduced a HalfedgeGraph concept http://www.cgal.org/Manual/latest/doc_html/cgal_manual/BGL_ref/Concept_Halfe... where one has global functions in order to walk along the border of a face, and go from an outgoing edge via the opposite incoming edge to a neighbor face.
FWIW I would certainly use a light-weight, header-only, generic half-edge data structure which would provide vertices, edges, faces, as well as the appropriate iterators etc. I've hacked together something myself over here: https://github.com/aewallin/openvoronoi/blob/master/src/common/halfedgediagr... however that code is not in the style of boost-libraries, and makes some assumptions on the template parameters TEdgeProperties and TFaceProperties (these could/should be concept-checked I guess). I'm always adding Faces to the graph and never deleting Faces, so I haven't provided a function for deleting Faces. The face-container is hard-coded to std::vector (and thus face_descriptor is unsigned int). In addition to CGAL there's also GTS (http://gts.sourceforge.net/) and OpenMesh (http://www.openmesh.org/) which provide similar functionality. All of these seem to be under slightly different not necessarily compatible licenses! Anders