Planar straight-line graph

Point-set triangulations are maximal PSLGs in the sense that it is impossible to add straight edges to them while keeping the graph planar.

For some graphs, such as Delaunay triangulations, both metric and topological properties are of importance.

The winged-edge data structure is the oldest of the three, but manipulating it often requires complicated case distinctions.

The halfedge data structure stores both orientations of an edge and links them properly, simplifying operations and the storage scheme.

The Quadedge data structure stores both the planar subdivision and its dual simultaneously.