Reprezentare plană ascendentă

O reprezentare plană ascendentă a unui grafic aciclic direcționat  este o încorporare a graficului în spațiul euclidian , în care muchiile sunt reprezentate ca curbe monotone crescătoare neintersectante . Adică, o curbă care reprezintă orice muchie trebuie să aibă proprietatea că orice linie orizontală o intersectează cel mult într-un punct și nici două muchii nu se pot intersecta decât la capete [1] [2] . În acest sens, este un caz ideal pentru desenarea grafică stratificată , un stil de reprezentare grafică în care curbele monotone se pot intersecta, dar în care numărul de intersecții este minim.

Descrieri

Un graf aciclic direcționat trebuie să fie plan pentru a avea o reprezentare plană ascendentă, dar nu orice graf aciclic plan are o astfel de reprezentare. Dintre toate graficele aciclice planare direcționate cu o singură sursă (un vârf care nu are arce de intrare) și un sink (un vârf care nu are arce de ieșire), graficele cu reprezentări plane ascendente sunt grafice st -planare , grafice plane în care sursa și sink aparțin aceleiași și aceleiași fețe pentru cel puțin o încorporare a unui graf plan. Mai general, un graf G are o reprezentare plană ascendentă dacă și numai dacă este direcționat, aciclic și este un subgraf al unui graf st -plan pe același set de vârfuri [3] [4] [5] [6] .

Într-o imbricare ascendentă, setul de arce de intrare și de ieșire incidente la fiecare vârf urmează succesiv în ordinea ciclică a arcelor de la vârf. O încorporare plană a unui graf aciclic direcționat dat se spune că este bimodală dacă are această proprietate. De asemenea, unghiul dintre două arce consecutive cu aceeași orientare la un punct dat poate fi etichetat mic dacă este mai mic decât , sau mare dacă este mai mare decât . Fiecare chiuvetă trebuie să aibă exact un unghi mare, iar orice vârf care nu este nici sursă, nici chiuvetă nu trebuie să aibă un unghi mare. În plus, fiecare față interioară a reprezentării trebuie să aibă două unghiuri minore mai multe decât unghiuri majore, iar fața exterioară trebuie să aibă două unghiuri mai mari decât unghiuri minore. Atribuirea corectă  este marcarea colțurilor, care satisface proprietățile descrise. Orice atașament din amonte are un scop valid. Dimpotrivă, orice graf aciclic direcționat care are o încorporare plană bimodală cu atribuirea corectă are o reprezentare plană ascendentă care poate fi construită în timp liniar [7] [8] [9] [10] .

O altă descriere este posibilă pentru graficele cu o singură sursă. În acest caz, înglobarea plană în sus trebuie să aibă originea pe fața exterioară și orice ciclu nedirecționat din grafic trebuie să aibă cel puțin un vârf la care ambele arce ale ciclului sunt de intrare (de exemplu, vârful din partea superioară a figurii). ). În schimb, dacă o încorporare are ambele aceste proprietăți, atunci este echivalentă cu o înglobare în amonte [11] [12] [13] .

Complexitate computațională

Se știe că unele cazuri speciale de verificare a planarității în sus se pot face în timp polinomial :

Totuși, problema determinării dacă un graf aciclic planar direcționat multisursă, multisink are o reprezentare plană ascendentă este NP-complet [33] [34] [35] .

Desenul liniilor și cerințele zonei

Teorema lui Fari afirmă că orice graf planar are o reprezentare în care muchiile sunt reprezentate prin segmente de linie și același lucru este valabil și pentru o reprezentare plană ascendentă - orice graf plan ascendent are o reprezentare plană ascendentă cu arce sub formă de segmente de linie [36] ] [37] . O reprezentare ascendentă rectilinie a unui graf st -planar redus tranzitiv poate fi obținută folosind tehnica de desen dominant cu toate vârfurile având coordonate întregi în rețea [38] [37] . Cu toate acestea, unele alte grafice plane ascendente pot necesita arie exponențială pentru toate reprezentările lor planare ascendente rectilinie [36] [37] . Dacă încorporarea este fixă, chiar și graficele în serie paralelă direcționate și arborii direcționați pot necesita o zonă exponențială [36] [39] [40] .

Diagrame Hasse

Reprezentările plane crescătoare sunt deosebit de importante pentru diagramele Hasse ale mulțimilor parțial ordonate , deoarece aceste diagrame trebuie de obicei desenate într-un stil ascendent. În ceea ce privește teoria grafurilor, aceasta corespunde grafurilor aciclice direcționate reduse tranzitiv . Un astfel de grafic poate fi format dintr-o relație de ordine parțială de acoperire, iar ordinea parțială în sine formează o relație de accesibilitate în grafic. Dacă un poset are un element minim, are un element maxim și are o reprezentare plană ascendentă, el formează în mod necesar o rețea , o mulțime în care orice pereche de elemente are o singură limită inferioară cea mai mare și o singură limită superioară cea mai mică [41] [ 42] . Diagrama Hasse a unei rețele este plană dacă și numai dacă dimensiunea sa ordinală nu depășește doi [43] [44] . Totuși, unele ordine parțiale de dimensiunea doi cu elemente minime și maxime nu au o reprezentare plană ascendentă (luăm ordinea definită de închiderea tranzitivă a ordinului ).

Note

  1. ↑ Garg, Tamassia, 1995 .
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 .
  3. ↑ Garg, Tamassia, 1995 , p. 111–112.
  4. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 172–179, §6.1 Includerea într-un grafic Planarst .
  5. ↑ Di Battista, Tamassia, 1988 .
  6. ^ Kelly, 1987 .
  7. ↑ Garg, Tamassia, 1995 , p. 112–115.
  8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 180–188, §6.2 Unghiuri în desenele în sus.
  9. ↑ 1 2 3 Bertolazzi, Di Battista, 1991 .
  10. ↑ 1 2 3 Bertolazzi, Di Battista, Liotta, Mannino, 1994 .
  11. ↑ Garg, Tamassia, 1995 , p. 115.
  12. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209–210, §6.7.2 Cicluri interzise pentru digrafele cu o singură sursă.
  13. ↑ Thomassen, 1989 .
  14. ↑ Garg, Tamassia, 1995 , p. 119.
  15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 179.
  16. ↑ Garg, Tamassia, 1995 , p. 119–121.
  17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 188–192, §6.3 Testarea planarității în sus a digrafelor încorporate.
  18. ↑ Abbasi, Healy, Rextin, 2010 .
  19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 191–192.
  20. ↑ Garg, Tamassia, 1995 , p. 125–126.
  21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209, §6.7.1 Digraf exterior planar.
  22. ↑ Papakostas, 1995 .
  23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , p. 212, §6.7.4 Unele clase de digrafe plane în sus.
  24. ↑ Didimo, Giordano, Liotta, 2009 .
  25. ↑ Di Battista, Liu, Rival, 1990 .
  26. ↑ Garg, Tamassia, 1995 , p. 122–125.
  27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 195–200, §6.5 Testarea optimă de planaritate ascendentă a digrafelor cu o singură sursă.
  28. ↑ Hutton, Lubiw, 1996 .
  29. ↑ Bertolazzi, Di Battista, Mannino, Tamassia, 1998 .
  30. ↑ Chan, 2004 .
  31. ↑ 12 Healy , Lynch, 2006 .
  32. ↑ Junger, Leipert, 1999 .
  33. ↑ Garg, Tamassia, 1995 , p. 126–132.
  34. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 201–209, §6.6 Testarea planarității în sus este NP-complet.
  35. ↑ Garg, Tamassia, 2001 .
  36. ↑ 1 2 3 Di Battista, Frati, 2012 , p. 149–151, §5 Desene în sus.
  37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
  38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 112–127 §4.7 Desene de dominanță.
  39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
  40. ↑ Frati, 2008 .
  41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 210–212 §6.7.3 Structuri interzise pentru zăbrele.
  42. ↑ Platt, 1976 .
  43. ↑ Garg, Tamassia, 1995 , p. 118.
  44. ↑ Baker, Fishburn, Roberts, 1972 .

Literatură

Recenzii și tutoriale Muncă de cercetare