Эстетические критерии

Эстетические критерии (aesthetic criteria) специфицируют такие свойства изображений графов, которые желательно применять в такой наибольшей степени, как только это возможно, чтобы повысить наглядность изображения. Широко используются следующие эстетические критерии.

Минимизация пересечений. Если изображение графа содержит много пересечений ребер, то трудно проследить взглядом, какие вершины связаны между собой. В идеале желательно иметь плоские (т. е. совсем без пересечений) изображения, но, к сожалению, не каждый граф является планарным. Нужно отметить, что необходимость минимизации пересечений возникает и как техническое требование, например, при проектировании интегральных схем.

Минимизация общего числа сгибов. Этот критерий особенно важен для ортогонального размещения, поскольку человеческий глаз может легко прослеживать связь по ребру, не имеющему сгибов вообще, либо по ребру с небольшим количеством сгибов, не описывающем странные зигзаги на рисунке. Критерий является также важным с технической точки зрения, поскольку при конструировании СБИС сгибы являются потенциальными местами неприятности.

Минимизация области размещения. Способность построения небольшого размера изображений является существенной для многих применений, связанных с визуализацией графа, в которых экономия места на экране представляется весьма важным. Этот критерий применим только тогда, когда используемые соглашения не позволяют изображению произвольным образом уменьшать масштаб, например, при сетчатом изображении или при прямолинейном изображении, требующем, чтобы соседние вершины отстояли друг от друга не менее, чем на единичное расстояние. Площадь размещения может формально определяться различными способами. Например, можно ее определять через площадь минимального выпуклого многоугольника, покрывающего рисунок (выпуклый каркас), или как площадь покрывающего рисунок наименьшего прямоугольника с горизонтальными и вертикальными сторонами.

Максимизация углового разрешения. Этот критерий, требующий максимизации минимального угла между двумя ребрами, инцидентными одной и той же вершине, приобретает в настоящее время особую важность. Если граф изображается на экране монитора с низким разрешением, важно, чтобы ребра расходились как можно шире. Этот критерий особенно важен при прямолинейных изображениях.

Минимизация общей длины ребер. Критерий минимизации суммы длин ребер является осмысленным, только если используемые соглашения не позволяют произвольным образом уменьшать масштаб изображения графа.

Минимизация длины ребра. Как и предыдущий, критерий минимизации максимальной длины ребра имеет смысл только тогда, когда нельзя произвольным образом уменьшать масштаб изображения графа.

Унификация длин ребер. Этот критерий предполагает минимизацию максимального различия в длинах между линиями, изображающими ребра графа.

Минимизация сгибов на ребре. Минимизируется максимальное число сгибов на одном ребре изображения графа.

Унификация сгибов. Минимизируется максимальное различие по числу сгибов между парами различных ребер изображения графа.

Максимальная симметричность. При изображении графа в наибольшей степени демонстрируется существующая симметрия графа. Этот эстетический критерий поддается большей формализации за счет введения математической модели симметрии графов и их изображений.

Минимизация коэффициента сторон. Критерий минимизирует отношение длины большей стороны к длине меньшей стороны у наименьшего прямоугольника с горизонтальными и вертикальными сторонами, который покрывает изображение графа. Рисунок с высоким коэффициентом сторон будет трудно разместить на экране монитора, даже если он занимает площадь скромного размера.

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

Литература

• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.