У меня есть график орграфа G = (V, E), который я хотел бы перерисовать, потому что в настоящее время он очень грязный. Это блок-схема, которая визуализируется, и поскольку | V |> 1000 и каждое v в V имеет более 1 исходящего фронта, его очень трудно отследить на глаз. Например; узел в левом нижнем углу соединен ребром с узлом в верхнем правом углу. Например, было бы лучше, если бы эти два узла были расположены рядом друг с другом. Слишком много краев, и каждый из них трудно отследить.
У меня есть доступ и я могу изменить (x, y) координаты всех вершин. Я хотел бы перерисовать G, сохранив его текущую структуру, более удобную для человека. Я думал, что минимизация количества пересекающихся ребер может быть чем-то, с чего можно начать.
Есть ли алгоритм, который может помочь мне перерисовать этот график?
У меня вопрос, как мне назначить (x, y) координаты каждому v в V, чтобы он был лучше организован и легче отслеживался и читался? Как мне выразить эти требования формально? Стоит ли идти с эвристикой, если это NP? Здесь - пример несколько организованного графа, а , это - что-то грязное (хотя и намного меньше, чем то, с чем я имею дело).
Любая помощь будет принята с благодарностью. Спасибо.
РЕДАКТИРОВАТЬ: Я все еще ищу точечный ответ. Я исследовал плоские прямые и ортогональные методы рисования, но у меня есть длинные исследовательские работы. То, что я ищу, - это реализация, псевдокод или, по крайней мере, кое-что, чтобы начать меня.
РЕДАКТИРОВАТЬ 2: Я не пытаюсь отобразить график. Вход для алгоритма должен быть graph G (composed of V and E), а выход {(xi, yi) for each vi in V}