В вычислительной геометрии и геометрической теории графов планарный прямолинейный граф (или прямолинейный плоский граф , или плоский прямолинейный граф ), сокращенно PSLG , представляет собой вложение планарного графа в плоскость таким образом, что его ребра отображаются в прямолинейные отрезки. [1] Теорема Фари (1948) утверждает, что любой планарный граф имеет такой вид вложения.
В вычислительной геометрии PSLG часто называют плоскими подразделениями , предполагая или утверждая, что подразделения являются многоугольными, а не имеют криволинейных границ.
PSLG могут служить в качестве представлений различных карт , например, географических карт в географических информационных системах . [2]
Частными случаями PSLG являются триангуляции ( полигональная триангуляция , точечная триангуляция ). Точечные триангуляции являются максимальными PSLG в том смысле, что к ним невозможно добавить прямые ребра, сохраняя при этом планарность графа. Триангуляции имеют многочисленные приложения в различных областях.
PSLG можно рассматривать как особый вид евклидовых графов . Однако при обсуждении евклидовых графов основной интерес представляют их метрические свойства, т. е. расстояния между вершинами, тогда как для PSLG основной интерес представляют топологические свойства. Для некоторых графов, таких как триангуляции Делоне , важны как метрические, так и топологические свойства.
Существует три хорошо известных структуры данных для представления PSLG, это структура данных Winged-edge , Halfedge и Quadedge . Структура данных winged-edge является старейшей из трех, но манипулирование ею часто требует сложных различий регистров. Это связано с тем, что ссылки на ребра не хранят направление ребра, а направления ребер вокруг грани не обязательно должны быть согласованными. Структура данных halfedge хранит обе ориентации ребра и связывает их должным образом, упрощая операции и схему хранения. Структура данных Quadedge хранит как плоское подразделение, так и его двойственное одновременно. Ее записи состоят явно только из записей ребер, по четыре для каждого ребра, и в упрощенной форме она подходит для хранения PSLG. [3]