Avaliação e extensão de técnicas de aceleração para minimização de cruzamentos ótimos em desenhos de gráficos em camadas

Um gráfico em camadas é uma categoria importante de gráfico na qual cada nó é atribuído a uma camada, e as camadas são desenhadas como linhas paralelas ou radiais. Eles são comumente usados para exibir dados temporais ou gráficos hierárquicos. Pesquisas anteriores demonstraram que minimizar o cruzamento de arestas é o critério mais importante a considerar ao buscar melhorar a legibilidade desses gráficos. Embora existam abordagens heurísticas para minimização de cruzamentos, estamos interessados em abordagens ótimas para o problema que priorizam a legibilidade humana sobre a escalabilidade computacional. Nosso objetivo é melhorar a utilidade e aplicabilidade de tais métodos ótimos, entendendo e melhorando sua escalabilidade para gráficos maiores. Este artigo categoriza e avalia as formulações de programação linear de última geração para minimização exata de cruzamentos e descreve nove novas técnicas, além de técnicas existentes, que poderiam acelerar plausivelmente o algoritmo de otimização. Por meio de uma avaliação computacional, exploramos o efeito de cada técnica no tempo de cálculo e como as técnicas se ajudam ou se inibem mutuamente, permitindo que pesquisadores e praticantes as adaptem às características de seus gráficos. Nossas técnicas de melhor desempenho renderizaram uma melhoria mediana de 2,5–17×, dependendo do resolvedor utilizado, proporcionando-nos a capacidade de criar layouts ótimos mais rapidamente e para gráficos maiores. Fornecemos uma implementação de código aberto de nossa metodologia em Python, onde os usuários podem escolher quais combinações de técnicas ativar de acordo com seu caso de uso. Uma cópia gratuita deste artigo e todo o material suplementar, conjuntos de dados utilizados e código-fonte estão disponíveis em https://osf.io/5vq79.