For faster navigation, this Iframe is preloading the Wikiwand page for Planar straight-line graph.

Planar straight-line graph

An example of planar straight-line graph

In computational geometry and geometric graph theory, a planar straight-line graph (or straight-line plane graph, or plane straight-line graph), in short PSLG, is an embedding of a planar graph in the plane such that its edges are mapped into straight-line segments.[1] 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 maps in geographical information systems.[2]

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.

Representations

[edit]

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.[3]

Problems in terms of PSLG

[edit]
  • 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".

See also

[edit]

References

[edit]
  1. ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
  2. ^ Nagy, George; Wagle, Sharad (June 1979), "Geographic Data Processing", ACM Computing Surveys, 11 (2): 139–181, doi:10.1145/356770.356777, S2CID 638860
  3. ^ Handbook of Data Structures and Applications, D. P. Mehta and S. Sahni, 2005, ISBN 1-58488-435-5, chapter 17
{{bottomLinkPreText}} {{bottomLinkText}}
Planar straight-line graph
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?