Укладки графов: метрики эстетики

Задача укладки графа — сопоставление вершинам координат в пространстве — редко оказывается в центре внимания. Гораздо чаще говорят о поиске кратчайших путей, потоках, изоморфизмах, кластеризации и других задачах, ценность которых очевидна. На их фоне задача укладки кажется периферийной.

Однако опыт исследовательской команды Graph Algorithm в Chebyshev Research Center показывает: без хорошей визуализации графа невозможно успешно завершить проект, а визуализация невозможна без корректной укладки. Критерии её качества зависят от цели, но в любом случае они формализуются через метрики эстетики.

На лекции мы обсудим несколько таких метрик и подходы к их вычислению.