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