Самый быстрый алгоритм планаризации графов
Я использую Processing для разработки навигационной системы для сложных данных и процессов. В рамках этого я довольно глубоко погрузился в компоновку графиков. Это все весело, и мое мнение об алгоритмах компоновки таково: force-directed предназначен для sissies (просто посмотрите на его масштаб ... хаха), проекция собственного вектора — это круто, слои Сугиямы выглядят хорошо, но быстро терпят неудачу на графических графах, и хотя я до сих пор полагался на собственные векторы, мне нужно минимизировать пересечения ребер, чтобы действительно добраться до точки данных. Я знаю, я знаю NP-complete и т. д.
Я должен добавить, что у меня есть некоторый хороший успех от применения xy бокса и использования перестановки, подобной Сугияме, чтобы уменьшить пересечения краев между строками и столбцами. Viz: график (| V|=90,средний градус log| В|) может перейти от 11000 пересечений -> 1500 (по коробчатым собственным векторам) -> 300 путем чередования перестановок строк и столбцов для уменьшения пересечений.
Но местные минимумы... что бы это ни было, он держится вокруг этой отметки, и результат не так ясен, как мог бы быть. Мои исследования освещенного показывают мне, что я действительно хочу использовать алгоритм планаризации, как то, что они используют для VLSI:
- Используйте BFS или что-то еще, чтобы сделать максимальный планарный подграф 1.а. Расположение планарного подграфа красиво
- Умно добавьте выдающиеся ребра для восстановления исходного графика
Пожалуйста, ответьте своими мыслями об алгоритме планаризации fastest, вы можете углубиться в любые конкретные оптимизации, с которыми вы были знакомы.
Спасибо большое!