Площа (візуалізація графів)

Площа в задачах візуалізації графів — числова характеристика якості графічного подання графа.

Визначення характеристики залежить від вибраного стилю візуалізації. У техніці, в якій вершини розташовуються на цілочисельній ґратці, площу подання можна визначити як площу найменшого розташованого паралельно осям обмежувального прямокутника для подання, тобто як добуток найбільшої різниці координат ${\displaystyle x}$ двох вершин та найбільшої різниці координат ${\displaystyle y}$ двох вершин. Для інших стилів подання, в яких вершини розташовуються вільніше, подання можна звести до масштабу, за якого пара найближчих вершин має одиничну відстань, після чого площу подання можна визначити як найменший обмежувальний прямокутник малюнка. Альтернативно, площу можна визначити як площу опуклої оболонки подання, знову ж таки, за відповідного масштабу^[1].

Поліноміальні межі

Для намальованого з прямими ребрами планарного графа з ${\displaystyle n}$ вершинами оптимальною межею площі малюнка в гіршому випадку буде ${\displaystyle \Theta (n^{2})}$. Граф укладених трикутників вимагає такої площі незалежно від того, як він укладений^[2], і відомі деякі методи, які дозволяють намалювати планарні графи з максимум квадратичною площею подання^[3][4]. Двійкові дерева і дерева обмеженого степеня як загальніший випадок мають подання з лінійною або майже лінійною площею, що залежить від стилю малюнка^{[5][6][7][8][9]}. Будь-який зовніпланарний граф має зовніпланарне подання з прямолінійними ребрами і субквадратичною від числа вершин площею^[10][11], а якщо дозволено злами або схрещення, то зовніпланарні графи мають подання з майже лінійною площею^[12][13]. Однак подання паралельно-послідовних графів вимагає площі, більшої від добутку ${\displaystyle n}$ на суперполілогарифмічну величину, навіть у разі дозволу малювати ребра у вигляді ламаних^[14].

Експоненціальні межі

Деякі стилі подання можуть показати експоненціальне зростання площі, так що ці стилі можуть виявитися придатними лише для невеликих графів. Прикладом є висхідне планарне подання планарних спрямованих ациклічних графів, площа яких для подання графа з ${\displaystyle n}$ вершинами у гіршому випадку може бути пропорційною ${\displaystyle 2^{n}}$^[15]. Навіть планарні дерева можуть вимагати експоненціальної площі, якщо вони намальовані прямолінійними відрізками, які зберігають фіксований циклічний порядок навколо кожної вершини і мають бути розташовані з рівними відстанями від вершини^[16].