Rezoluție unghiulară (teoria grafurilor)

Rezoluția unghiulară a unui desen grafic se referă la unghiul cel mai ascuțit format de oricare două muchii care se întâlnesc la același vârf din desen.

Proprietăți

Relația cu gradul de vârf

Foreman și colab .[1] au observat că orice desen al unui grafic cu muchii de segment cu gradul maxim d are o rezoluție unghiulară care nu depășește — dacă v este un vârf cu gradul d , atunci muchiile incidente la v împart spațiul din jurul vârfului v în d pene cu unghi total , iar cea mai mică dintre aceste pene trebuie să aibă un unghi care să nu depășească . Mai strict, dacă graficul este d - regulat , acesta trebuie să aibă o rezoluție unghiulară mai mică decât , deoarece aceasta este cea mai bună rezoluție care poate fi obținută pentru un vârf de pe corpul convex al figurii.

Relația cu colorarea graficului

După cum arată Foreman și colaboratorii [1] , cea mai mare rezoluție unghiulară posibilă a unui grafic G este strâns legată de numărul cromatic al pătratului graficului G 2 , adică un grafic cu același set de vârfuri în care fiecare perechea de vârfuri este conectată printr-o muchie dacă distanța dintre ele în graficul G nu depășește două. Dacă graficul G 2 poate fi colorat cu culori, atunci G poate fi desenat cu rezoluție unghiulară pentru orice , prin alocarea de culori diferite vârfurilor unui -gon obișnuit și plasând fiecare vârf al lui G lângă un vârf de poligon cu aceeași culoare. Folosind această construcție, ei au arătat că orice grafic cu gradul maxim d are un model cu o rezoluție unghiulară proporțională cu 1/ d 2 . Această limită este aproape exactă - au folosit o metodă probabilistă pentru a demonstra existența graficelor cu un grad maxim d , ale căror desene au rezoluție unghiulară .

Existența unor modele optime

Forman și colaboratorii [1] au dat un exemplu care arată că există grafice care nu au modele cu rezoluția unghiulară maximă posibilă. Dimpotrivă, aceste grafice au o familie de desene ale căror rezoluții unghiulare tind la o anumită valoare limitată, dar nu o ating. Mai exact, au prezentat un grafic cu 11 vârfuri care are un model cu o rezoluție unghiulară de orice , dar nu are un model cu o rezoluție unghiulară de exact .

Clase speciale de grafice

Copaci

Orice arbore poate fi desenat în așa fel încât marginile să fie distribuite uniform în jurul fiecărui vârf, o proprietate cunoscută sub numele de rezoluție unghiulară perfectă . Mai mult, dacă muchiile pot fi permutate liber în jurul fiecărui vârf, atunci un astfel de model este posibil fără intersecții cu muchii de lungime una sau mai multe, iar întregul model este plasat într- un dreptunghi cu zonă polinomială . Totuși, dacă ordonarea circulară a muchiilor în jurul fiecărui vârf este deja specificată ca parte a enunțului problemei, atunci obținerea unei rezoluții unghiulare fără încrucișări poate necesita uneori o zonă exponențială [2] [3] .

Grafice exterioare

Rezoluția unghiulară perfectă nu este întotdeauna posibilă pentru graficele planare exterioare , deoarece vârfurile de pe corpul convex al unui model cu un grad mai mare decât unu nu pot avea margini incidente cu acesta distribuite uniform în jurul vârfului. Totuși, orice grafic exterior planar cu gradul maxim d are un desen exterior planar cu o rezoluție unghiulară proporțională cu 1/ d [4] [5] .

Grafice plane

Pentru graficele plane cu gradul maxim d , tehnica de colorare a pătratului graficului a lui Foreman (et al.) [1] produce un desen cu o rezoluție unghiulară proporțională cu 1/ d , deoarece pătratul unui grafic plan trebuie să aibă un număr cromatic proporțional cu d . Wegner a presupus în 1977 că numărul cromatic al pătratului unui graf plan nu depășește și se știe că numărul cromatic nu depășește [6] [7] . Cu toate acestea, modelul obținut prin această tehnică nu este, în general, plan.

Pentru unele grafice plane, rezoluția unghiulară optimă a unui desen plan cu segmente de dreaptă este O(1/ d 3 ) , unde d este gradul graficului [5] . În plus, astfel de modele pot fi forțate să aibă muchii foarte lungi, mai lungi decât factorul exponențial de la cea mai scurtă margine a modelului. Malitz și Papakostas [4] au folosit teorema de ambalare a cercului pentru a arăta că orice graf plan cu gradul maxim d are un model plan a cărui rezoluție unghiulară în cel mai rău caz este o funcție exponențială a lui d și independentă de numărul de vârfuri ale grafului.

Complexitate computațională

Problema determinării dacă un graf dat cu gradul maxim d are un model cu rezoluție unghiulară este NP-hard chiar și în cazul special d =4 [1] [8] . Cu toate acestea, pentru unele clase limitate de desene, inclusiv desene de copaci, în care extinderea frunzelor la infinit oferă o partiție convexă a planului, precum și desenele de grafice plane, în care fiecare față delimitată este un poligon simetric central, un desenul cu rezoluție unghiulară optimă poate fi găsit în timp polinomial [ 9] [10] .

Istorie

Rezoluția unghiulară a fost determinată de Forman și colab .. [1] .

Deși inițial a fost definit pentru desenele graficelor cu muchii drepte, autorii ulterioare au investigat rezoluția unghiulară a desenelor în care muchiile sunt poligonale [11] [12] , arce circulare [13] [2] sau spline [14] [15] .

Rezoluția unghiulară a unui grafic este strâns legată de rezoluția sa de intersecție, unghiurile formate de intersecțiile din desenul graficului. În special, desenarea graficelor în unghi drept caută o reprezentare care să asigure că toate acele unghiuri sunt unghiuri drepte , care este cel mai mare unghi de intersecție posibil [16]

Note

  1. ↑ 1 2 3 4 5 6 Formann, Hagerup, Haralambides et al., 1993 .
  2. ↑ 1 2 Duncan, Eppstein, Goodrich et al., 2011 .
  3. ↑ Halupczok, Schulz, 2011 .
  4. ↑ 1 2 Malitz, Papakostas, 1994 .
  5. ↑ 1 2 Garg, Tamassia, 1994 .
  6. ↑ Kramer, Kramer, 2008 .
  7. ↑ Molloy, Salavatipour, 2005 .
  8. ↑ Garg, Tamassia, 1995 .
  9. ↑ Carlson, Eppstein, 2007 .
  10. ↑ Eppstein, Wortman, 2011 .
  11. ↑ Kant, 1996 .
  12. ↑ Gutwenger, Mutzel, 1998 .
  13. ↑ Cheng, Duncan, Goodrich, Kobourov, 1999 .
  14. ↑ Brandes, Shubina, Tamassia, 2000 .
  15. ↑ Finkel, Tamassia, 2005 .
  16. ↑ Didimo, Eades, Liotta, 2009 .

Literatură