Area (grafvisualisering)

Området i grafvisualiseringsproblem  är en numerisk egenskap för kvaliteten på den grafiska representationen av en graf.

Definitionen av en egenskap beror på den valda renderingsstilen. I en teknik där hörn är ordnade på ett heltalsrutnät , kan arean av en representation definieras som arean av den minsta parallella begränsningsrutan för representationen, det vill säga produkten av den största skillnaden i koordinaterna för två hörn och den största skillnaden i koordinaterna för två hörn. För andra renderingsstilar, där hörnen är åtskilda mer fritt, kan representationen skalas så att det närmaste paret av hörn har enhetsavstånd, varefter representationsarean kan definieras som den minsta begränsningsrutan i ritningen. Alternativt kan area definieras som arean av representationens konvexa skrov , återigen i lämplig skala [1] .

Polynomgränser

För en plan graf med hörn ritade med raka kanter är den optimala gränsen för ritningsområdet i värsta fall . En kapslad triangelgraf kräver detta område oavsett hur grafen är kapslad [2] , och vissa metoder är kända som tillåter att rita plana grafer med en maximal kvadratisk representationsarea [3] [4] . Binära träd och träd av avgränsad grad som ett mer allmänt fall har representationer med linjär eller nästan linjär yta, beroende på ritstilen [5] [6] [7] [8] [9] . Varje ytterplanär graf har en yttre planrepresentation med raka linjesegment som kanter och en area som är subkvadratisk av antalet hörn [10] [11] , och om veck eller skärningar är tillåtna , så har ytterplanära grafer representationer med nästan linjär area [12] [ 13] . Representationen av parallellsekventiella grafer kräver dock en area som är större än produkten av det superpolylogaritmiska värdet, även om det är möjligt att rita kanter i form av streckade linjer [14] .

Exponentiella gränser

Vissa presentationsstilar kan visa exponentiell areatillväxt, så dessa stilar kanske bara är lämpliga för små grafer. Ett exempel är den nedifrån och upp plana representationen av planriktade acykliska grafer , vars area för en vertexgrafrepresentation kan vara proportionell i värsta fall [15] . Även plana träd kan kräva exponentiell yta om de är ritade med raka linjesegment som upprätthåller en fast cyklisk ordning runt varje vertex och måste placeras på lika avstånd runt vertexen [16] .

Anteckningar

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

Litteratur