Площадь (графическое изображение)
Размер ограничивающей рамки графического рисунка

В графическом рисовании площадь, занимаемая чертежом, является общепринятым способом измерения его качества.

Определение

Для стиля рисования, в котором вершины размещены на целочисленной решетке , площадь рисунка может быть определена как площадь наименьшего ограничивающего прямоугольника рисунка, выровненного по осям: то есть, это произведение наибольшей разницы в x -координатах двух вершин с наибольшей разницей в y -координатах. Для других стилей рисования, в которых вершины размещены более свободно, рисунок может быть масштабирован так, чтобы ближайшая пара вершин имела расстояние один друг от друга, после чего площадь может быть снова определена как площадь наименьшего ограничивающего прямоугольника рисунка. В качестве альтернативы, площадь может быть определена как площадь выпуклой оболочки рисунка, снова после соответствующего масштабирования. [1]

Полиномиальные границы

Для прямолинейных рисунков планарных графов с n вершинами оптимальная граница наихудшего случая площади рисунка равна Θ( n 2 ). Граф вложенных треугольников требует такой площади независимо от того, как он вложен, [2] и известно несколько методов, которые могут рисовать планарные графы с площадью не более квадратичной. [3] [4] Двоичные деревья и деревья ограниченной степени в более общем случае имеют рисунки с линейной или почти линейной площадью, в зависимости от стиля рисования. [5] [6] [7] [8] [9] Каждый внешнепланарный граф имеет прямолинейный внешнепланарный рисунок с площадью, субквадратичной по количеству вершин, [10] [11] Если допускаются изгибы или пересечения , то внешнепланарные графы имеют рисунки с почти линейной площадью. [12] [13] Однако для рисования последовательно-параллельных графов требуется площадь, большая, чем n, умноженная на суперполилогарифмический множитель, даже если ребра можно нарисовать как полилинии . [14]

Экспоненциальные границы

В отличие от этих полиномиальных границ, некоторые стили рисования могут демонстрировать экспоненциальный рост своих площадей, подразумевая, что эти стили могут быть пригодны только для небольших графов. Примером является восходящее планарное рисование планарных направленных ациклических графов , где площадь рисунка с n вершинами может быть пропорциональна 2 n в худшем случае. [15] Даже плоские деревья могут потребовать экспоненциальной площади, если они должны быть нарисованы с прямыми ребрами, которые сохраняют фиксированный циклический порядок вокруг каждой вершины и должны быть равномерно распределены вокруг вершины. [16]

Ссылки

  1. ^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассиа, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графов: алгоритмы визуализации графов (1-е изд.), Prentice Hall, стр.  14–15 , ISBN 0133016153.
  2. ^ Долев, Дэнни ; ​​Лейтон, Том ; Трики, Ховард ( 1984 ), «Планарное вложение планарных графов» (PDF) , Достижения в области вычислительных исследований , 2 : 147–161
  3. ^ de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1988), «Малые множества, поддерживающие вложения Фари планарных графов», Двадцатый ежегодный симпозиум ACM по теории вычислений , стр.  426–433 , doi : 10.1145/62212.62254 , ISBN 0-89791-264-0, S2CID  15230919.
  4. ^ Шнайдер, Вальтер (1990), «Встраивание планарных графов в сетку», Труды 1-го симпозиума ACM/SIAM по дискретным алгоритмам (SODA), стр.  138–148 , ISBN 978-0-89871-251-3.
  5. ^ Crescenzi, P.; Di Battista, G.; Piperno, A. (1992), «Заметка об алгоритмах оптимальной площади для восходящих рисунков бинарных деревьев», Computational Geometry Theory & Applications , 2 (4): 187– 200, doi :10.1016/0925-7721(92)90021-J, MR  1196545.
  6. ^ Гарг, Ашим; Гудрич, Майкл Т .; Тамассиа, Роберто (1996), «Планарные восходящие рисунки деревьев с оптимальной площадью», Международный журнал вычислительной геометрии и приложений , 6 (3): 333– 356, doi :10.1142/S0218195996000228, MR  1409650.
  7. ^ Чан, ТМ (2002), «Почти линейная область, ограниченная для рисования бинарных деревьев», Algorithmica , 34 (1): 1– 13, doi :10.1007/s00453-002-0937-x, MR  1912924, S2CID  5122671.
  8. ^ Чан, Тимоти М .; Гудрич, Майкл Т .; Косараджу, С. Рао ; Тамассиа, Роберто (2002), «Оптимизация площади и соотношения сторон в прямолинейных ортогональных чертежах деревьев», Computational Geometry Theory & Applications , 23 (2): 153– 162, doi :10.1016/S0925-7721(01)00066-9, MR  1922928.
  9. ^ Гарг, Ашим; Русу, Адриан (2004), «Прямые линии рисунков бинарных деревьев с линейной площадью и произвольным соотношением сторон», Журнал графовых алгоритмов и приложений , 8 (2): 135–160 , doi : 10.7155/jgaa.00086 , MR  2164808.
  10. ^ Гарг, Ашим; Русу, Адриан (2007), «Площадно-эффективные плоские прямолинейные рисунки внешнепланарных графов», Дискретная прикладная математика , 155 (9): 1116– 1140, doi : 10.1016/j.dam.2005.12.008 , MR  2321019.
  11. ^ Ди Баттиста, Джузеппе; Фрати, Фабрицио (2009), «Чертежи внешнепланарных графов небольшой площади», Algorithmica , 54 (1): 25–53 , doi : 10.1007/s00453-007-9117-3, MR  2496664, S2CID  2814656.
  12. ^ Бидл, Тереза ​​(2002), «Рисование внешнепланарных графов в O ( n  log  n ) области», Рисование графов : 10-й Международный симпозиум, GD 2002, Ирвайн, Калифорния, США, 26–28 августа 2002 г., Пересмотренные статьи , Заметки лекций по информатике, т. 2528, Springer, стр.  54–65 , doi : 10.1007/3-540-36151-0_6 , ISBN 978-3-540-00158-4, МР  2063411.
  13. ^ Ди Джакомо, Эмилио; Дидимо, Вальтер; Лиотта, Джузеппе; Монтеккиани, Фабрицио (2013), «Требования к площади для рисунков графов с небольшим количеством пересечений на ребро», Computational Geometry Theory & Applications , 46 (8): 909–916 , doi : 10.1016/j.comgeo.2013.03.001 , MR  3061453.
  14. ^ Фрати, Фабрицио (2011), «Улучшенные нижние границы требований к площади последовательно-параллельных графов», Рисование графов : 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспект лекций по информатике, т. 6502, стр.  220–225 , doi : 10.1007/978-3-642-18469-7_20 , ISBN 978-3-642-18468-0, г-н  2781267.
  15. ^ Ди Баттиста, Джузеппе; Тамассиа, Роберто; Толлис, Иоаннис Г. (1992), «Требование площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (4): 381– 401, doi : 10.1007/BF02187850 , MR  1148953.
  16. ^ Дункан, Кристиан А.; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Нёлленберг, Мартин (2013), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Дискретная и вычислительная геометрия , 49 (2): 157– 182, arXiv : 1009.0581 , doi : 10.1007/s00454-012-9472-y, MR  3017904, S2CID  5000871.
Получено с "https://en.wikipedia.org/w/index.php?title=Area_(graph_drawing)&oldid=1263508592"