Площадь (рисунок графика) - Area (graph drawing)

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

Определение

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

Полиномиальные оценки

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

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

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

Рекомендации

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