Планарный прямолинейный граф (ППЛ граф, . PSLG) — это вложение планарного графа в плоскость таким образом, что его рёбра отображаются в отрезки прямых. Теорема Фари (1948) утверждает, что любой планарный граф имеет такого рода вложение.
В вычислительной геометрии ППЛ графы часто называют планарными разбиениями, подразумевая, что эти разбиения являются полигональными, то есть, не имеют криволинейных границ.
ППЛ графы могут использоваться для представления различных карт, например, географических карт в геоинформационных системах.
Частными случаями ППЛ графов являются триангуляции (многоугольников и множеств точек). Триангуляции множеств точек — это максимальные ППЛ графы в том смысле, что к ним невозможно добавить прямые рёбра, сохраняя при этом планарность графа. Триангуляции находят многочисленные применения в различных областях.
ППЛ графы можно рассматривать как особый вид . Однако в обсуждениях, касающихся евклидовых графов, основной интерес представляют их метрические свойства, то есть расстояния между вершинами, тогда как для ППЛ графов основной интерес представляют топологические свойства. Для некоторых графов, таких как триангуляции Делоне, важны как метрические, так и топологические свойства.
Представления Существует три хорошо известные структуры для представления ППЛ графов, это структура крылатых рёбер, полуребро и четырёхзначная рёберная структура данных. Структура крылатых рёбер наиболее старая из них, но работа с ней часто требует сложного различения случаев. Это связано с тем, что ссылки на рёбра не хранят их направление, а направления рёбер вокруг грани не обязательно согласованы. Структура данных «полуребро» хранит обе ориентации ребра и правильно их связывает, упрощая операции и схему хранения. Четырёхзначная рёберная структура данных одновременно хранит планарное разбиение и его двойственный граф. Её записи состоят исключительно из записей рёбер, по четыре записи на каждое ребро, и в упрощенном виде она подходит для хранения ППЛ графов .
Задачи в терминах ППЛ графов Локализация точки. Для заданной точки определить, какой грани ППЛ графов точка принадлежит. Наложение данных на карту. Найти наложение двух ППЛ графов (карт), что представляет собой разбиение плоскости двумя одновременно вложенными ППЛ графами. В ГИС эта проблема известна как "наложение тематических карт".
См. также Двусвязный список рёбер, структура представления данных в ППЛ
Примечания
Категория:Геометрические алгоритмы Категория:Геометрические графы Категория:Планарные графы