Combinatorial optimization problems for explicit edge bundling
| Autor: | Ferreira, Joelma de Moura |
|---|---|
| Přispěvatelé: | Nascimento, Hugo Alexandre Dantas do, Foulds, Les, Freitas, Carla Maria Dal Sasso, Paulovich, Fernando, Longo, Humberto José, Soares, Telma Woerle de Lima |
| Jazyk: | portugalština |
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Biblioteca Digital de Teses e Dissertações da UFG Universidade Federal de Goiás (UFG) instacron:UFG |
| Popis: | A união de arestas em feixes é uma técnica para agrupar, alinhar, coordenar e posicionar a representação de arestas em um desenho de grafo, de modo que os conjuntos de arestas pareçam ser reunidos em estruturas visuais compartilhadas, ou seja, feixes. O objetivo final é reduzir a poluição visual do desenho melhorando a forma como ele transmite informações. Esta tese apresenta uma formulação geral para problemas de união explícita de arestas, como um problema formal de otimização. Essa formulação pode ser usada para definir e comparar problemas de união de arestas. Ainda, são definidos quatro problemas de otimização de união explícita de arestas, que têm por objetivo minimizar o número total de feixes, em conjunto com outros aspectos. Um algoritmo evolucionário é descrito. O algoritmo foi testado com sucesso em três dos problemas relacionados aplicados a instâncias do mundo real. Os resultados experimentais demonstram a eficácia e a aplicabilidade do algoritmo evolutivo proposto para ajudar a resolver problemas de união de arestas em feixes formalmente definidos como um modelo de otimização. Edge bundling is a technique to group, align, coordinate and position the depiction of edges in a graph drawing, so that sets of edges appear to be brought together into shared visual structures, i.e. bundles. The ultimate goal is to reduce clutter to improve how it conveys information. This thesis provides a general formulation for the explicity edge bundling problems, as a formal combinatorial optimization problem. This allows for the definition and comparison of edge bundling problems. In addition, we present four explicity edge bundling optimization problems that address minimizing the total number of bundles, in conjunction with other aspects, as the main goal. An evolutionary edge bundling algorithm is described. The algorithm was successfully tested by solving three related problems applied to real-world instances. The reported experimental results demonstrate the effectiveness and the applicability of the proposed evolutionary algorithm to help resolve edge bundling problems formally defined as optimization models. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|