Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

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

Полиномиальные границы [ править ]

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

Экспоненциальные границы [ править ]

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

Ссылки [ править ]

  1. ^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Прентис Холл, стр. 14–15, ISBN 0133016153.
  2. ^ Долев, Дэнни ; Лейтон, Том ; Трики, Ховард (1984), «Планарное вложение плоских графов» (PDF) , « Достижения в области компьютерных исследований» , 2 : 147–161
  3. ^ де Фрейссе, Юбер; Пах, Янош ; Поллак, Ричард (1988), «Маленькие наборы поддержки Fary вложения плоских графов», двадцатый ежегодный ACM симпозиум по теории вычислений , С. 426-433,. DOI : 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, DOI : 10.1016 / 0925-7721 (92) 90021- J , MR 1196545 .
  6. ^ Гарг, Ашим; Гудрич, Майкл Т .; Tamassia, Роберто (1996), "Planar вверх дерева чертежи с оптимальной областью", Международный журнал вычислительной геометрии и приложений , 6 (3): 333-356, DOI : 10,1142 / S0218195996000228 , МР 1409650 .
  7. ^ Чан, TM (2002), «Граница почти линейной области для рисования двоичных деревьев», Algorithmica , 34 (1): 1–13, DOI : 10.1007 / s00453-002-0937-x , MR 1912924 , S2CID 5122671   CS1 maint: обескураженный параметр ( ссылка ).
  8. ^ Чан, Тимоти М .; Гудрич, Майкл Т .; Косараджу, С. Рао ; Tamassia, Роберто (2002), "Оптимизация отношение площадей и аспект прямолинейных ортогональных чертежей дерева", Вычислительная теория и приложения Геометрия , 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 , МР 2321019 .
  11. ^ Ди Баттиста, Джузеппе; Frati, Фабрицио (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 г., Revised Papers , Lecture Notes в области компьютерных наук, 2528 ., Springer, С. 54-65, DOI : 10.1007 / 3-540-36151-0_6 , MR 2063411  CS1 maint: обескураженный параметр ( ссылка ).
  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 , MR 2781267 .
  15. ^ Ди Баттиста, Джузеппе; Тамассия, Роберто; Tollis, Иоаннис Г. (1992), "Площадь требование и отображение симметрии плоских вверх чертежей", Дискретная и вычислительная геометрия , 7 (4): 381-401, DOI : 10.1007 / BF02187850 , МР 1148953 .
  16. ^ Дункан, Кристиан А .; Эпштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г .; Нелленбург, Мартин (2013), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Дискретная и вычислительная геометрия , 49 (2): 157–182, arXiv : 1009.0581 , doi : 10.1007 / s00454-012-9472-y , MR 3017904 , S2CID 5000871  .