Planar straight-line graph

In computational geometry, a planar straight-line graph, in short PSLG, (or straight-line plane graph, or plane straight-line graph) is a term used for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. Fáry's theorem (1948) states that every planar graph has this kind of embedding. In computational geometry, a planar straight-line graph, in short PSLG, (or straight-line plane graph, or plane straight-line graph) is a term used for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. Fáry's theorem (1948) states that every planar graph has this kind of embedding. In computational geometry, PSLGs have often been called planar subdivisions, with an assumption or assertion that subdivisions are polygonal. A PSLG without vertices of degree 1 defines a subdivision of the plane into polygonal regions and vice versa. The absence of vertices of degree 1 simplifies descriptions of various algorithms, but it is not essential. PSLGs may serve as representations of various maps, e.g., geographical maps in geographical information systems. Special cases of PSLGs are triangulations (polygon triangulation, point set triangulation). Point set triangulations are maximal PSLGs in the sense that it is impossible to add straight edges to them while keeping the graph planar. Triangulations have numerous applications in various areas. PSLGs may be seen as a special kind of Euclidean graphs. However, in discussions involving Euclidean graphs, the primary interest is their metric properties, i.e., distances between vertices, while for PSLGs the primary interest is the topological properties. For some graphs, such as Delaunay triangulations, both metric and topological properties are of importance. There exist three well-known data strucutres for representing PSLGs, these are the Winged-edge data structure, Halfedge, and Quadedge. The winged-edge data structure is the oldest of the three, but manipulating it often requires complicated case distinctions. This is because edge references do not store the edge direction, and the directions of edges around a face need not be consistent. 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. Its records consist explicitly only of edge records, four for each edge, and in a simplified form it is suitable for storing PSLGs.