Thanks, Andrii, Louis, Like Louis, I try to use Boost.Polygon Voronoi diagram for medial axis computation. Since Voronoi diagram is stored as DCEL, it is not difficult to represent it as a combination of two dual graphs. The "primal" bidirected graph has Voronoi vertices as its vertices and (finite) halfedges as edges. The "dual" graph has Voronoi cells as its vertices; half-edges "connect" adjacent cells. This graph is also bi-directed. I think this understanding of DCEL is rather common; I believe CGAL applies similar approach to provide Boost Graph adapters for its DCEL arrangements. For my purposes I am writing the adapters on my own. Iterator parts are straight-forward. For efficiency it is also useful to convert some internals into "property maps". For example, color map is already provided, one has only to wrap it into boost::property_map with correct access functions. Similarly, the fact that vertices are packed into continuous storage gives us an efficient "vertex to integer" bimap, an important ingredient for many search algorithms from Boost Graph library. As the next step I hope to implement your discussion on vertices connected to infinity, vertices in holes etc.using Boost.Graph. Andrii, I would be glad to share this code with you and Boost.Polygon users. Thanks, -Michael