| dbo:abstract
|
- 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 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 rather than having curved boundaries. 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. (en)
- Плаский прямолінійний граф (ППЛГ) — це термін використовуваний в обчислювальній геометрії для вкладення планарного графу на площині так, що його ребра переходять у прямолінійні відрізки. Теорема Фарі (1948) стверджує, що кожний планарний граф має такий тип вкладення. В обчислювальній геометрії ППЛГ часто називають пласким розбиттям, з припущенням або ствердженням, що розбиття полігональне. Максимальним пласким розбиттям називають таке розбиття, що неможливо додати жодне ребро, яке б поєднувало дві вершини, так щоб не порушити пласкість. ППЛГ без вершин степені 1 визначає розбиття площини на полігональні регіони і навпаки. Відсутність вершин степені 1 спрощує опис багатьох алгоритмів, але це не суттєво. ППЛГ може слугувати як представлення різноманітних мап. Наприклад, географічна карта в геоінформаційній системі. Особливим випадком ППЛГ є тріангуляції: тріангуляція багатокутника, Тріангуляція множини точок. Багатоточкова тріангуляція є максимальною ППЛГ в тому сенсі, що неможливо додати до них прямолінійні ребра, так щоб граф залишився планарним. Тріангуляції мають численні застосування в різних областях. ППЛГ може розглядатися як особливий вид . Однак в дискусіях, пов'язаних з евклідовими графами основний інтерес представляє їх метричні властивості, тобто, відстані між вершинами, в той час як для ППЛГ основний інтерес пов'язаний з топологічними властивостями. Для деяких графів, таких як тріангуляція Делоне, як метричні, так і топологічні властивості мають важливе значення. (uk)
|
| rdfs:comment
|
- 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 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 rather than having curved boundaries. (en)
- Плаский прямолінійний граф (ППЛГ) — це термін використовуваний в обчислювальній геометрії для вкладення планарного графу на площині так, що його ребра переходять у прямолінійні відрізки. Теорема Фарі (1948) стверджує, що кожний планарний граф має такий тип вкладення. В обчислювальній геометрії ППЛГ часто називають пласким розбиттям, з припущенням або ствердженням, що розбиття полігональне. Максимальним пласким розбиттям називають таке розбиття, що неможливо додати жодне ребро, яке б поєднувало дві вершини, так щоб не порушити пласкість. (uk)
|
