Doubly-connected edge list

The doubly -connected edge list ( DCEL, doubly linked list of edges ) is a data structure that represents a contiguous planar graphs embedded in the plane. The data structure is used in the computational geometry.

Definition

Let G = (V, E) be a planar graph, V = the set of nodes, E = the set of edges.

The DCEL stores, for each edge of the graph an entry with the data ( ):

• : Start node of the edge
• : End node of the edge
• Name of the surface on the left side of the edge
• Name of the surface on the right side of the edge
• : Pointer to the first edge node encountered when rotating counter-clockwise around the edge
• Analogously, this time with node

Example

The following entries are saved for the graph in the figure:

Applications and Other

With the help of references to the successor edges can efficiently all the edges are determined by preset endpoint, as well as all edges on the boundary of a given area.

As a doubly -connected edge list the slightly different structure Half- Edge data structure is also referred to. DCEL is a variant of the winged -edge data structure.

If you add additional edges, which is obtained when one clockwise and turns, you get the quad edge data structure ( QEDS ). With it, the edges of surfaces and from the node outgoing edges can be traversed in both directions. Another advantage is that one obtains the QEDS the dual graph where each edge is replaced by its respective dual edge.