Плоский прямолінійний граф

Плаский прямолінійний граф (ППЛГ) — це термін використовуваний в обчислювальній геометрії для вкладення планарного графу на площині так, що його ребра переходять у прямолінійні відрізки. Теорема Фарі (1948) стверджує, що кожний планарний граф має такий тип вкладення.

Приклад планарного прямолінійного графу

В обчислювальній геометрії ППЛГ часто називають пласким розбиттям, з припущенням або ствердженням, що розбиття полігональне. Максимальним пласким розбиттям називають таке розбиття, що неможливо додати жодне ребро, яке б поєднувало дві вершини, так щоб не порушити пласкість.

ППЛГ без вершин степені 1 визначає розбиття площини на полігональні регіони і навпаки. Відсутність вершин степені 1 спрощує опис багатьох алгоритмів, але це не суттєво.

ППЛГ може слугувати як представлення різноманітних мап. Наприклад, географічна карта в геоінформаційній системі.

Особливим випадком ППЛГ є тріангуляції: тріангуляція багатокутника, Тріангуляція множини точок. Багатоточкова тріангуляція є максимальною ППЛГ в тому сенсі, що неможливо додати до них прямолінійні ребра, так щоб граф залишився планарним. Тріангуляції мають численні застосування в різних областях.

ППЛГ може розглядатися як особливий вид ^[en]. Однак в дискусіях, пов'язаних з евклідовими графами основний інтерес представляє їх метричні властивості, тобто, відстані між вершинами, в той час як для ППЛГ основний інтерес пов'язаний з топологічними властивостями. Для деяких графів, таких як тріангуляція Делоне, як метричні, так і топологічні властивості мають важливе значення.

Задачі в термінах ППЛГ

• Локалізація точки. Для певної точки, знайти якій грані ППЛГ вона належить.
• . Знайти накладення двох ППЛГ (карт), що є розбиттям площини одночасно двома ППЛГ.

Див. також

• Подвійно зв'язаний список ребер, структура даних для ППЛГ

Примітки

1. Препарата і Шеймос (1985). Обчислювальна геометрія - Вступ. Springer-Verlag. 1-е видання: ; 2-й випуск, виправлений і розширений, 1988: ;.