Planar straight-line graph (PSLG) is a term used in computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

 for an embedding

Graph embedding

In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...

 of a planar graph

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 the plane

Plane (mathematics)

In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...

 such that its edges are mapped into straight line segments. Fáry's theorem

Fáry's theorem

In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn...

 (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 algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s, but it is not essential.

PSLGs may serve as representations of various map

Map

A map is a visual representation of an area—a symbolic depiction highlighting relationships between elements of that space such as objects, regions, and themes....

s, e.g., geographical maps in geographical information systems.

Special cases of PSLGs are triangulations (polygon triangulation

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....

, point set triangulation

Point set triangulation

A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs....

). Point set triangulations are maximal PSLGs in the sense that it is impossible to add straight edges to them. 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

Delaunay triangulation

In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...

s, both metric and topological properties are of importance.

Problems in terms of PSLG

• Point location
  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 , motion planning, and computer aided design ....
  
  . For a query point, find which face of the PSLG it belongs to.
• Map overlay. 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
  Thematic map
  A thematic map is a type of map or chart especially designed to show a particular theme connected with a specific geographic area. These maps "can portray physical, social, political, cultural, economic, sociological, agricultural, or any other aspects of a city, state, region,nation , or...
  
   overlay".

See also

• Doubly connected edge list, a data structure to represent a PSLG
• Local feature size
  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....