Obszar (rysowanie wykresu)
W rysowaniu wykresów obszar używany przez rysunek jest powszechnie stosowanym sposobem pomiaru jego jakości .
Definicja
W przypadku stylu rysowania, w którym wierzchołki są umieszczone na siatce liczb całkowitych , obszar rysunku można zdefiniować jako obszar najmniejszego prostokąta ograniczającego wyrównanego z osią rysunku: to znaczy iloczyn największej różnicy w x -współrzędne dwóch wierzchołków o największej różnicy we współrzędnych y . W przypadku innych stylów rysowania, w których wierzchołki są rozmieszczone swobodniej, rysunek można przeskalować tak, aby najbliższe pary wierzchołków były oddalone od siebie, po czym obszar można ponownie zdefiniować jako obszar najmniejszej ramki ograniczającej rysunek. Alternatywnie, obszar można zdefiniować jako obszar wypukłej otoczki rysunku, ponownie po odpowiednim przeskalowaniu.
Granice wielomianów
W przypadku rysunków liniowych grafów planarnych z n wierzchołkami optymalnym ograniczeniem najgorszego przypadku na obszarze rysunku jest Θ( n 2 ). Wykres zagnieżdżonych trójkątów wymaga tak dużego obszaru bez względu na to, jak jest osadzony, i znanych jest kilka metod, które umożliwiają rysowanie wykresów planarnych o polu co najwyżej kwadratowym. Drzewa binarne , a bardziej ogólnie drzewa o ograniczonym stopniu, mają rysunki z obszarem liniowym lub prawie liniowym, w zależności od stylu rysowania. Każdy graf w płaszczyźnie zewnętrznej ma prosty rysunek w płaszczyźnie zewnętrznej z obszarem podkwadratowym pod względem liczby wierzchołków. Jeśli dozwolone są zagięcia lub skrzyżowania , wówczas grafy w płaszczyźnie zewnętrznej mają rysunki z obszarem prawie liniowym. Jednak rysowanie grafów szeregowo-równoległych wymaga obszaru większego niż n pomnożonego przez współczynnik superpolilogarytmiczny, nawet jeśli krawędzie można narysować jako polilinie .
Granice wykładnicze
W przeciwieństwie do tych ograniczeń wielomianowych, niektóre style rysowania mogą wykazywać wykładniczy wzrost w swoich obszarach, co sugeruje, że te style mogą być odpowiednie tylko dla małych wykresów. Przykładem jest płaskie rysowanie skierowane w górę płaskich grafów acyklicznych , gdzie obszar rysunku n -wierzchołków może być proporcjonalny do 2 n w najgorszym przypadku. Nawet platany mogą wymagać powierzchni wykładniczej, jeśli mają być narysowane z prostymi krawędziami, które zachowują ustalony porządek cykliczny wokół każdego wierzchołka i muszą być równomiernie rozmieszczone wokół wierzchołka.