In
computational geometry and
geometric graph theory, 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
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.
When some object X is said to be embedded in another object Y, the embedding is giv ...
of a
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
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 rather than having curved boundaries.
PSLGs may serve as representations of various
maps, e.g.,
geographical map
Cartography (; from grc, χάρτης , "papyrus, sheet of paper, map"; and , "write") is the study and practice of making and using maps. Combining science, aesthetics and technique, cartography builds on the premise that reality (or an i ...
s in
geographical information systems
A geographic information system (GIS) is a type of database containing geographic data (that is, descriptions of phenomena for which location is relevant), combined with software tools for managing, analyzing, and visualizing those data. In a ...
.
Special cases of PSLGs are triangulations (
polygon triangulation
In computational geometry, polygon triangulation is the partition of a polygonal area ( simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is .
Triangulations may ...
,
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 triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
s, both metric and topological properties are of importance.
Representations
There exist three well-known data structures 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.
[''Handbook of Data Structures and Applications, D. P. Mehta and S. Sahni, 2005, {{ISBN, 1-58488-435-5'', chapter 17 ]
Problems in terms of PSLG
*
Point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided ...
. For a query point, find which face of the PSLG it belongs to.
*
Map overlay
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
. Find the overlay of two PSLGs (maps), which is the subdivision of the plane by the two simultaneously embedded PSLGs. In GIS this problem is known as "
thematic map
A thematic map is a type of map that portrays the geographic pattern of a particular subject matter (theme) in a geographic area. This usually involves the use of map symbols to visualize selected properties of geographic features that are no ...
overlay".
See also
*
Doubly connected edge list, a data structure to represent a PSLG
*
Local feature size Local feature size refers to several related concepts in computer graphics and computational geometry for measuring the size of a geometric object near a particular point.
*Given a smooth manifold M, the local feature size at any point x \in M ...
References
Geometric algorithms
Geometric graphs
Planar graphs