Визуализация комплексных концептуальных структур это ключевой компонент инструментов поддержки для многих приложений в науке и инженерии. Граф это абстрактная структура используемая для моделирования информации. Графы используются для представления информации, которая может быть смоделирована как объекты и связи между объектами.
Кнут в 1963 году представил алгоритм для рисования блок-схем.
Области применения рисования графов:
- software engineering (data flow diagrams, subroutine-call graphs, program nesting trees, object-oriented class hierarchies);
- databases (entity-relationship diagrams);
- information systems (organization charts);
- real-time systems (Petri nets, state-transition diagrams);
- decision support systems (PERT networks, activity trees);
- VLSI (circuit schematics);
- artificial intelligence (knowledge-representation diagrams);
- logic programming (SLD-trees);
- medical science (concept latices);
- biology (evolutionary trees);
- chemistry (molecular drawings);
- civil engineering (floorplan maps);
- cartography (map schematics).
Направления:
- discrete mathematics (topological graph theory, geometric graph theory, order theory);
- algorithms (graph algorithms, data structures, computational geometry, VLSI);
- human-computer interaction (visual languages, graphical user interfaces, software visualization).
Вершины представляются символами (точками), а ребра представляются простыми открытыми кривыми Жордана (simple open Jordan curves), которые соединяют символы представляющие вершины. В математике преобладает рисование прямолинейных ребер, а у проектировщиков схем и БД (circuit and database designers) преобладают ортогональные чертежи, в которых ребра состоят из горизонтальных и вертикальных сегментов.
Полезность чертежа зависит от его читабельности (выразительности). Чем быстрее и яснее понимается значение графа, тем лучше. Есть определенные критерии эстетики. Например, минимизация пересечений между ребрами (планарность), и отображение симметрий. В общем нужно стремиться снизить количество изгибов и пересечений. Также нужно избегать пустой траты пространства на странице или экране компьютера. Ввиду этого многие задачи рисования графов могут быть формализованы как задачи многокритериальной оптимизации (например, сконструировать чертеж минимальной площади и наименьшим количеством изгибов и пересечений). Часто приходиться изменять значение одного показателя за счет другого (trade-offs).
Разделяй и властвуй (divide and conquer) вечная (evergreen) парадигма в информатике (computer science). Применяется для рисования деревьев и series-parallel диграфов. Используется для тестирования на планарность.
Методы основанные на сетевом потоке (network flow) применяются для конструирования планарных ортогональных чертежей (planar orthogonal drawings) в погруженном планарном графе (embedded planar graph) с минимальным количеством изгибов.
Поточные техники также применяются для решения проблемы тестирования диграфов на upward планарность.
Инкрементальные техники применяются для решения проблемы планаризации графов.
Конструирование ортогональных grid чертежей не планарных графов основывается на начальном ориентировании (orienting) графа, а затем последовательном рисовании его вершин следуя порядку ориентирования (order of orientation).
Иерархические подходы применяются для создания polyline чертежей диграфов с вершинами упорядоченными в горизонтальные слои. Этот подход может быть применен к любым диграфам.
Есть несколько техник берущих на входе граф и моделирующих систему сил отражающую предпочтения пользователя. Прямолинейный чертеж получается из равновесной конфигурации (equilibrium configuration) системы сил.
--
--
