Площадь (визуализация графов)

У этого термина существуют и другие значения, см. Площадь (значения).

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

Определение характеристики зависит от избранного стиля визуализации. В технике, в которой вершины располагаются на целочисленной решётке, площадь представления может быть определена как площадь наименьшего расположенного параллельно осям ограничивающего прямоугольника для представления, то есть как произведение наибольшей разности координат ${\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].