Doubly connected edge list

<p>The doubly connected edge list (DCEL), also known as half-edge data structure, is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> to represent an <a href="/facts/Graph_embedding/IyBA3ttM">embedding</a> of a <a href="/facts/Planar_graph/plREagr9">planar graph</a> in the <a href="/facts/Plane_(geometry)/tAUtRFcn">plane</a>, and <a href="/facts/Polytope/a76nXrL0">polytopes</a> in <a href="/facts/Three-dimensional_space/KAqKWUbS">3D</a>. This data structure provides efficient manipulation of the topological information associated with the objects in question (vertices, edges, faces). It is used in many <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> of <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> to handle polygonal subdivisions of the plane, commonly called <a href="/facts/Planar_straight-line_graph/7MN0MycS">planar straight-line graphs</a> (PSLG). For example, a <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagram</a> is commonly represented by a DCEL inside a bounding box. 
</p><p>This data structure was originally suggested by Muller and Preparata for representations of 3D <a href="/facts/Convex_polyhedra/2pRHcRgC">convex polyhedra</a>. Simplified versions of the data structure, as described here, only consider <a href="/facts/Connected_graph/FSNjsYhz">connected graphs</a>, but the DCEL structure may be extended to handle disconnected graphs as well by introducing dummy edges between disconnected components.
</p>

Doubly connected edge list open-in-new

Doubly connected edge list