Войти
В чертеже графика область, используемая чертежом, обычно используется для измерения его качества.
Для стиля рисования, в котором вершины размещаются на целочисленная решетка, область чертежа может быть определена как область наименьшего выровненного по оси ограничивающего прямоугольника чертежа: то есть это произведение наибольшая разница в x-координатах двух вершин с наибольшей разницей в y-координатах. Для других стилей рисования, в которых вершины размещены более свободно, рисунок можно масштабировать так, чтобы ближайшая пара вершин находилась на расстоянии друг от друга, после чего область снова может быть определена как область наименьшая ограничивающая рамка рисунка. В качестве альтернативы, площадь может быть определена как площадь выпуклой оболочки чертежа, опять же после соответствующего масштабирования.
Для прямолинейных чертежей плоских графов с n вершинами, оптимальная граница площади рисунка в худшем случае равна is (n). Граф вложенных треугольников требует такой большой площади независимо от того, как он встроен, и известно несколько методов, которые могут рисовать планарные графы с площадью не более квадратичной. В более общем смысле, иметь рисунки с линейной или почти линейной областью, в зависимости от стиля рисования. Каждый внешнепланарный граф имеет прямолинейный внешнепланарный чертеж с субквадратичной площадью по количеству вершин. Если разрешены изгибы или пересечения, то внешнепланарные графы имеют чертежи с почти линейная зона. Однако для рисования последовательно-параллельных графов требуется площадь больше n, умноженная на суперполилогарифмический коэффициент, даже если ребра можно нарисовать как полилинии.
В отличие от эти полиномиальные границы, некоторые стили рисования могут показывать экспоненциальный рост в своих областях, подразумевая, что эти стили могут подходить только для небольших графиков. Примером является направленный вверх плоский рисунок плоских направленных ациклических графов, где площадь рисунка с n вершинами может быть пропорциональна 2 в худшем случае. Даже плоские деревья могут потребовать экспоненциальной площади, если они должны быть нарисованы с прямыми краями, которые сохраняют фиксированный циклический порядок вокруг каждой вершины и должны быть равномерно распределены вокруг вершины.
