Graf planar cu muchii drepte

În geometria algoritmică^⁠(d) și teoria grafurilor geometrice, un graf planar cu muchii drepte (în engleză planar straight-line graph – PSLG) este un termen folosit pentru un graf planar încorporat într-un plan astfel încât muchiile acestuia să fie segmente de dreaptă. Teorema lui Fáry (1948) afirmă că orice graf planar poate fi adus la această formă.

Un exemplu de graf planar cu muchii drepte

În geometria algoritmică grafurile planare cu muchii drepte au fost adesea numite subdiviziuni plane, cu o presupunere sau aserțiune că subdiviziunile sunt mai degrabă poligonale decât să aibă frontiere curbe.

Grafurile planare cu muchii drepte pot servi ca reprezentări ale diferitelor hărți, de exemplu hărți topografice în sistemele de informații geografice.

Cazurile particulare ale grafurilor planare cu muchii drepte sunt triangulările (triangularea unui poligon, triangularea unei mulțimi de puncte). Triangulările mulțimilor de puncte sunt grafuri planare cu muchii drepte maxime în sensul că este imposibil să le fie adăugate alte muchii drepte, păstrând graf planar. Triangulările au numeroase aplicații în diverse domenii.

Grafurile planare cu muchii drepte pot fi văzute ca un tip special de grafuri geometrice (euclidiene). Totuși, în discuțiile care implică grafuri euclidiene, interesul principal îl reprezintă proprietățile metrice ale acestora, adică distanțele dintre vârfuri, în timp ce pentru cele planare cu muchii drepte interesul principal îl reprezintă proprietățile topologice. Pentru unele grafuri, cum ar fi triangulările Delaunay, atât proprietățile metrice, cât și cele topologice sunt importante.

Reprezentări

Există trei structuri de date binecunoscute pentru reprezentarea grafurilor planare cu muchii drepte, acestea sunt structura de date winged-edge^⁠(d) (în traducere literală latură înaripată), halfedge^⁠(d) (în traducere literală semilatură) și Quadedge^⁠(d) (în traducere literală latură cvadruplă). Structura de date „latură înaripată” este cea mai veche dintre cele trei, dar necesită adesea distingeri complicate de cazuri. Acest lucru se datorează faptului că datele referitoare la laturi nu stochează și direcția lor, iar direcțiile laturilor din jurul unei fețe nu trebuie să fie consecvente. Structura „semilatură” stochează ambele orientări ale unei laturi și le leagă corect, simplificând operațiunile și schema de stocare. Structura de date „latură cvadruplă” stochează atât subdiviziunea plană, cât și duala ei, simultan. Înregistrările sale constau în mod explicit numai din înregistrări ale laturilor, câte patru date pentru fiecare latură, iar într-o formă simplificată este potrivită pentru stocarea grafurilor planare cu muchii drepte.