Planar straight-line graph
- Planar straight-line graph
Planar straight-line graph (PSLG) is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. [cite book
author = Franco P. Preparata and Michael Ian Shamos | title = Computational Geometry - An Introduction | publisher = Springer-Verlag| year = 1985 | id = 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6] 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. 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.
Problems in terms of PSLG
*Point location. 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 overlay".
ee also
*Doubly-connected edge list, a data structure to represent a PSLG
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Straight skeleton — In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a… … Wikipedia
Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… … Wikipedia
Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 … Wikipedia
String graph — In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a string . Given a graph G , G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three… … Wikipedia
Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… … Wikipedia
List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Ruppert's algorithm — Input planar straight line graph Output conforming Delaunay triangulation … Wikipedia
