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