stringtranslate.com

Рисование графика

Графическое представление минутной части WWW с указанием гиперссылок .

Рисование графиков — это область математики и информатики , сочетающая методы геометрической теории графов и визуализации информации для получения двумерных изображений графиков , возникающих в результате таких приложений, как анализ социальных сетей , картография , лингвистика и биоинформатика . [1]

Рисунок графа или сетевой диаграммы — это графическое изображение вершин и ребер графа . Этот рисунок не следует путать с самим графиком: одному и тому же графику могут соответствовать самые разные макеты. [2] Говоря абстрактно, важно лишь то, какие пары вершин соединены ребрами. Однако в бетоне расположение этих вершин и ребер внутри чертежа влияет на его понятность, удобство использования, стоимость изготовления и эстетику . [3] Проблема усугубляется, если граф со временем меняется путем добавления и удаления ребер (динамическое рисование графа), и цель состоит в том, чтобы сохранить мысленную карту пользователя. [4]

Графические соглашения

Ориентированный график со стрелками, показывающими направления ребер.

Графы часто рисуются в виде диаграмм узел-связь, в которых вершины представлены в виде дисков, прямоугольников или текстовых меток, а края представлены в виде отрезков линий , полилиний или кривых на евклидовой плоскости . [3] Диаграммы узел-связь можно проследить до работ Псевдо-Лулля XIV-XVI веков, которые были опубликованы под именем Рамона Луллия , эрудита XIII века. Псевдо-Лулл ​​рисовал диаграммы такого типа для полных графов , чтобы анализировать все парные комбинации среди наборов метафизических понятий. [5]

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

Альтернативные соглашения для диаграмм узел-связь включают представления смежности, такие как упаковки кругов , в которых вершины представлены непересекающимися областями на плоскости, а ребра представлены смежностями между областями; представления пересечений , в которых вершины представлены непересекающимися геометрическими объектами, а ребра представлены их пересечениями; представления видимости, в которых вершины представлены областями на плоскости, а края представлены областями, которые имеют беспрепятственную линию обзора друг к другу; сливающиеся рисунки, на которых края представлены плавными кривыми внутри математических железнодорожных путей ; ткани, в которых узлы представлены горизонтальными линиями, а края - вертикальными линиями; [8] и визуализации матрицы смежности графа.

Меры качества

Для графических рисунков было определено множество различных показателей качества в попытке найти объективные средства оценки их эстетики и удобства использования. [9] Помимо выбора между различными методами компоновки одного и того же графика, некоторые методы компоновки пытаются напрямую оптимизировать эти показатели.

Плоский граф , нарисованный без перекрывающихся ребер

Методы компоновки

Силовая сетевая визуализация. [13]

Существует множество различных стратегий компоновки графиков:

Диаграмма дуги

Графические чертежи для конкретных приложений

Графики и графические рисунки, возникающие в других областях применения, включают:

Кроме того, этапы размещения и маршрутизации электронного проектирования (EDA) во многом аналогичны рисованию графов, как и проблема жадного встраивания в распределенные вычисления , а литература по рисованию графов включает несколько результатов, заимствованных из литературы EDA. Однако эти проблемы также различаются по нескольким важным аспектам: например, в EDA минимизация площади и длина сигнала более важны, чем эстетика, а проблема маршрутизации в EDA может иметь более двух терминалов на сеть, в то время как аналогичная проблема при построении графов вообще включает только пары вершин для каждого ребра.

Программное обеспечение

Интерфейс рисования графиков ( Gephi 0.9.1)

Программное обеспечение, системы и поставщики систем для рисования графиков включают:

Смотрите также

Сноски

  1. ^ Ди Баттиста и др. (1994), стр. vii–viii; Герман, Мелансон и Маршалл (2000), раздел 1.1, «Типичные области применения».
  2. ^ аб Ди Баттиста и др. (1994), с. 6.
  3. ^ аб Ди Баттиста и др. (1994), с. viii.
  4. ^ Мисуэ и др. (1995)
  5. ^ Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древнее и современное , Oxford University Press, стр. 7–37..
  6. ^ Холтен и ван Вейк (2009); Холтен и др. (2011).
  7. ^ Гарг и Тамассия (1995).
  8. ^ Лонгабо (2012).
  9. ^ Ди Баттиста и др. (1994), раздел 2.1.2, Эстетика, стр. 14–16; Покупка, Коэн и Джеймс (1997).
  10. ^ Ди Баттиста и др. (1994), стр. 14.
  11. ^ Ди Баттиста и др. (1994), с. 16.
  12. ^ аб Пач и Шарир (2009).
  13. ^ Опубликовано в Гранжане, Мартине (2014). «La connaissance est un reseau». Les Cahiers du Numérique . 10 (3): 37–54. дои : 10.3166/lcn.10.3.37-54. Архивировано из оригинала 27 июня 2015 г. Проверено 15 октября 2014 г.
  14. ^ Ди Баттиста и др. (1994), раздел 2.7, «Подход, направленный на силу», стр. 29–30, и глава 10, «Методы, направленный на силу», стр. 303–326.
  15. ^ Бекман (1994); Корен (2005).
  16. ^ Ди Баттиста и др. (1994), глава 5, «Поток и ортогональные рисунки», стр. 137–170; (Эйгльспергер, Фекете и Клау, 2001).
  17. ^ Герман, Мелансон и Маршалл (2000), Раздел 2.2, «Традиционная планировка – обзор».
  18. ^ Сугияма, Тагава и Тода (1981); Бастерт и Матушевский (2001); Ди Баттиста и др. (1994), Глава 9, «Многослойные рисунки орграфов», стр. 265–302.
  19. ^ Саати (1964).
  20. ^ Догрусоз, Мэдден и Мэдден (1997).
  21. ^ Ди Баттиста и др. (1994), раздел 4.7, «Рисунки доминирования», стр. 112–127.
  22. ^ Скотт (2000); Брандес, Фриман и Вагнер (2014).
  23. ^ Ди Баттиста и др. (1994), стр. 15–16, и глава 6, «Поток и восходящая плоскостность», стр. 171–214; Фриз (2004).
  24. ^ Заппони (2003).
  25. ^ Андерсон и Хэд (2006).
  26. ^ Ди Баттиста и Римондини (2014).
  27. ^ Бахмайер, Брандес и Шрайбер (2014).
  28. ^ «Graphviz и Dynagraph - инструменты рисования статических и динамических графиков», Джон Эллсон, Эмден Р. Ганснер, Элефтериос Кутсофиос, Стивен К. Норт и Гордон Вудхалл, в Jünger & Mutzel (2004).
  29. ^ GraphPlot. Архивировано 3 февраля 2014 г. в документации Wayback Machine Mathematica.
  30. ^ «Урок рисования графиков» . Архивировано из оригинала 12 сентября 2013 г. Проверено 27 сентября 2012 г.
  31. ^ Нахмансон, Робертсон и Ли (2008).
  32. ^ «Тюльпан - огромная структура визуализации графов», Дэвид Обер, в Junger & Mutzel (2004).
  33. ^ «yFiles - визуализация и автоматическое размещение графиков», Роланд Визе, Маркус Эйгльспергер и Михаэль Кауфманн, в Jünger & Mutzel (2004).
  34. ^ Тантау (2013); см. также старую презентацию GD 2012. Архивировано 27 мая 2016 г. на Wayback Machine.

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

Специализированные подтемы

Внешние ссылки