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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

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