Alue (kaavion visualisointi)

Graafisen visualisointiongelmien alue on graafin  graafisen esityksen laadun numeerinen ominaisuus.

Ominaisuuden määritelmä riippuu valitusta renderöintityylistä. Tekniikassa, jossa kärjet on järjestetty kokonaislukuruudukkoon , esityksen pinta-ala voidaan määritellä esityksen pienimmän yhdensuuntaisen rajoituslaatikon alueeksi, eli suurimman koordinaattieron tuloksi. kaksi kärkeä ja suurin ero kahden kärjen koordinaateissa . Muissa renderöintityyleissä, joissa kärjet on sijoitettu vapaammin, esitys voidaan skaalata niin, että lähimmällä pisteparilla on yksikköetäisyys , jonka jälkeen esitysalue voidaan määritellä piirustuksen pienimmäksi rajoituslaatikoksi. Vaihtoehtoisesti pinta-ala voidaan määritellä esityksen kuperan rungon alueeksi , jälleen sopivassa mittakaavassa [1] .

Polynomirajat

Tasograafille , jonka kärjet on piirretty suorilla reunoilla , piirustusalueen optimaalinen raja on pahimmassa tapauksessa . Sisäkkäinen kolmiograafi vaatii tämän alueen riippumatta siitä, miten graafi on sisäkkäin [2] , ja tunnetaan joitakin menetelmiä, jotka mahdollistavat tasokaavioiden piirtämisen, joilla on maksimi neliöllinen esitysalue [3] [4] . Binääripuilla ja yleisemmin rajatuilla puilla on piirustustyylistä riippuen lineaariset tai lähes lineaariset esitykset [5] [6] [7] [8] [9] . Jokaisella ulompitasoisella graafilla on ulompi esitysmuoto, jossa suorat janat ovat reunoja ja pinta-ala, joka on alikvadraattinen kärkien lukumäärästä [10] [11] , ja jos taivutukset tai leikkauspisteet ovat sallittuja, niin ulompitasoisissa graafisissa esityksissä on lähes lineaarinen pinta-ala [12] [ 13] . Rinnakkaisten peräkkäisten graafien esittäminen vaatii kuitenkin alueen, joka on suurempi kuin superpolylogaritmisen arvon tulo, vaikka olisi mahdollista piirtää reunoja katkoviivoina [14] .

Eksponentiaaliset rajat

Joissakin esitystyyleissä voi näkyä eksponentiaalista pinta-alan kasvua, joten nämä tyylit voivat sopia vain pienille kaavioille. Esimerkkinä on tasosuuntaisten asyklisten graafien alhaalta ylös -tasoesitys , jonka pinta-ala kärkigraafin esitykselle voi olla verrannollinen pahimmassa tapauksessa [15] . Jopa tasomaiset puut voivat vaatia eksponentiaalista pinta-alaa, jos ne on piirretty suorilla janoilla, jotka säilyttävät kiinteän syklisen järjestyksen kunkin kärjen ympärillä ja jotka on sijoitettava yhtä suurille etäisyyksille kärjen ympäriltä [16] .

Muistiinpanot

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

Kirjallisuus