Zona (vizualizare grafică)

Zona în problemele de vizualizare grafică  este o caracteristică numerică a calității reprezentării grafice a unui grafic.

Definiția unei caracteristici depinde de stilul de randare ales. Într-o tehnică în care vârfurile sunt aranjate pe o grilă întreagă , aria unei reprezentări poate fi definită ca aria celei mai mici casete paralele de delimitare pentru reprezentare, adică produsul celei mai mari diferențe în coordonatele lui două vârfuri și cea mai mare diferență în coordonatele a două vârfuri. Pentru alte stiluri de randare, în care vârfurile sunt distanțate mai liber, reprezentarea poate fi scalată astfel încât cea mai apropiată pereche de vârfuri să aibă distanța unitară, după care aria de reprezentare poate fi definită ca cea mai mică casetă de delimitare a desenului. Alternativ, aria poate fi definită ca aria carcasei convexe a reprezentării, din nou la o scară adecvată [1] .

Limite polinomiale

Pentru un graf plan cu vârfuri desenate cu muchii drepte , limita optimă a zonei de desen în cel mai rău caz este . Un grafic triunghi imbricat necesită această zonă indiferent de modul în care este imbricat graficul [2] , iar unele metode sunt cunoscute care permit trasarea graficelor plane cu o zonă maximă de reprezentare pătratică [3] [4] . Arborii binari și arborii de grad mărginit ca caz mai general au reprezentări cu zonă liniară sau aproape liniară, în funcție de stilul de desen [5] [6] [7] [8] [9] . Orice graf exterior planar are o reprezentare exterioară cu segmente de linie dreaptă ca muchii și o zonă subquadratică a numărului de vârfuri [10] [11] , iar dacă sunt permise îndoituri sau intersecții , atunci graficele outerplanare au reprezentări cu o zonă aproape liniară [12] [ 13] . Totuși, reprezentarea graficelor paralel-secvențiale necesită o suprafață mai mare decât produsul valorii superpolilogaritmice, chiar dacă este posibil să se deseneze muchii sub formă de linii întrerupte [14] .

Limite exponențiale

Unele stiluri de prezentare pot prezenta o creștere exponențială a zonei, astfel încât aceste stiluri pot fi potrivite numai pentru grafice mici. Un exemplu este reprezentarea plană de jos în sus a grafurilor aciclice plane direcționate , a căror zonă pentru reprezentarea unui graf cu vârfuri poate fi proporțională în cel mai rău caz [15] . Chiar și arborii plani pot necesita arie exponențială dacă sunt desenați cu segmente de linie dreaptă care mențin o ordine ciclică fixă ​​în jurul fiecărui vârf și trebuie distanțate la distanțe egale în jurul vârfului [16] .

Note

  1. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 14–15.
  2. ↑ Dolev, Leighton, Trickey, 1984 , p. 147–161.
  3. ↑ de Fraysseix, Pach și Pollack, 1988 , p. 426–433.
  4. ↑ Schnyder, 1990 , p. 138–148.
  5. ↑ Crescenzi, Di Battista, Piperno, 1992 , p. 187–200.
  6. ↑ Garg, Goodrich, Tamassia, 1996 , p. 333–356.
  7. ↑ Chan, 2002 , p. 1–13.
  8. ↑ Chan, Goodrich, Kosaraju, Tamassia, 2002 , p. 153–162.
  9. ↑ Garg, Rusu, 2004 , p. 135–160.
  10. ↑ Garg, Rusu, 2007 , p. 1116–1140.
  11. ↑ Di Battista, Frati, 2009 , p. 25–53.
  12. ↑ Biedl, 2002 , p. 54–65.
  13. ↑ Di Giacomo, Didimo, Liotta, Montecchiani, 2013 , p. 909–916.
  14. ↑ Frati, 2011 , p. 220–225.
  15. ↑ Di Battista, Tamassia, Tollis, 1992 , p. 381–401.
  16. ↑ Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2013 , p. 157–182.

Literatură