Параметризованные алгоритмы графического представления графов: различия между версиями

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