Terület (grafikon megjelenítése)

A gráfvizualizációs problémák területe a gráf  grafikus ábrázolásának minőségének numerikus jellemzője.

A jellemző meghatározása a választott megjelenítési stílustól függ. Egy olyan technikában, ahol a csúcsok egy egész rácson vannak elrendezve , az ábrázolás területe az ábrázolás legkisebb párhuzamos határolókeretének területeként definiálható , azaz a koordináták legnagyobb eltérésének szorzataként. két csúcs és a legnagyobb különbség két csúcs koordinátái között. Más renderelési stílusoknál, ahol a csúcsok szabadabban helyezkednek el, az ábrázolás méretezhető úgy, hogy a legközelebbi csúcspár egységnyi távolságú legyen, ami után az ábrázolási terület a rajz legkisebb határolódobozaként definiálható. Alternatív megoldásként a terület definiálható az ábrázolás domború házának területeként is , megfelelő léptékben [1] .

Polinomhatárok

Egyenes élekkel rajzolt csúcsokkal rendelkező síkgráf esetén a rajzterület optimális határa legrosszabb esetben a következő . Egy beágyazott háromszöggráfnak szüksége van erre a területre, függetlenül attól, hogy a gráf hogyan van beágyazva [2] , és ismertek olyan módszerek, amelyek lehetővé teszik sík gráfok rajzolását maximális másodfokú ábrázolási területtel [3] [4] . A bináris fák és a korlátos fokú fák általánosabb esetben lineáris vagy közel lineáris területtel rendelkeznek, a rajzstílustól függően [5] [6] [7] [8] [9] . Bármely külső síkbeli gráfnak van egy külső síkbeli ábrázolása, amelynek élei az egyenes szakaszok, és a csúcsok számának szubquadratikus területe [10] [11] , és ha a törések vagy metszéspontok megengedettek , akkor a külső síkbeli gráfok majdnem lineáris területtel rendelkeznek [12] [ 13] . A párhuzamos-szekvenciális gráfok ábrázolásához azonban a szuperpolilogaritmikus érték szorzatánál nagyobb területre van szükség , még akkor is, ha lehetséges szaggatott vonalak formájában éleket rajzolni [14] .

Exponenciális határok

Egyes megjelenítési stílusok exponenciális területnövekedést mutathatnak , így ezek a stílusok csak kis grafikonokhoz alkalmasak. Példa erre a síkbeli irányított aciklikus gráfok alulról felfelé történő síkbeli ábrázolása , amelyek területe a csúcsgráf-ábrázolás számára a legrosszabb esetben arányos lehet [15] . Még a síkfák is igényelhetnek exponenciális területet, ha olyan egyenes szakaszokkal rajzolják meg őket, amelyek rögzített ciklikus sorrendet tartanak fenn minden csúcs körül, és egyenlő távolságra kell elhelyezni őket a csúcs körül [16] .

Jegyzetek

  1. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 14–15.
  2. ↑ Dolev, Leighton, Trickey, 1984 , p. 147–161.
  3. ↑ de Fraysseix, Pach és 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.

Irodalom