Автоматическое расположение вершин на плоскости - Визуализация графа цитирования

Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она была поставлена в первых работах по этой теме.

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

    1. Между вершинами графа должно быть достаточно расстояния. 2. Связанные вершины должны находится рядом с друг другом, не связанные - в отдалении. 3. Ребра не должны пересекаться.

К сожалению, в общем случае все требования одновременно могут быть не достигнуты, например, без пересечений ребер можно нарисовать только определенное подмножество всех графов, которое называется "планарным", поэтому для остальных графов количество пересечений должно быть минимизировано. Также стоит заметить такие субъективные свойства, как "достаточно расстояния" и "рядом с друг другом", которые могут восприниматься по-разному различными людьми.

Похожие статьи




Автоматическое расположение вершин на плоскости - Визуализация графа цитирования

Предыдущая | Следующая