Orientador: Celmar Guimarães da Silva

Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia

Resumo: A utilização de grafos acíclicos direcionados permite a representação gráfica de estruturas hierárquicas, o que facilita encontrar padrões e tendências durante a análise dessas estruturas. A principal abordagem de desenho automático desses grafos divide seus vértices em camadas, de tal modo...

Resumo: A utilização de grafos acíclicos direcionados permite a representação gráfica de estruturas hierárquicas, o que facilita encontrar padrões e tendências durante a análise dessas estruturas. A principal abordagem de desenho automático desses grafos divide seus vértices em camadas, de tal modo que as arestas sempre apontem para uma mesma direção. Um dos principais critérios estéticos dessas estruturas visuais é evitar, sempre que possível, o cruzamento entre arestas, facilitando assim o entendimento do desenho. Os algoritmos de redução de cruzamentos devem também prover essa solução em um tempo inferior a 0,1 segundo, tornando mais apropriada sua utilização em estruturas visuais interativas. Nesta dissertação, pesquisou-se como uma estrutura de dados conhecida por árvore PQR poderia ser utilizada a fim de aperfeiçoar dois métodos de redução de cruzamentos: BC e MEDIAN. Dentre os novos métodos desenvolvidos, destacaram se: PQR_BC2 para o aperfeiçoamento do BC; PQR_M2 para o aperfeiçoamento do MEDIAN. Os resultados obtidos através da aplicação dos métodos a pacotes de grafos amplamente utilizados na literatura mostram que os métodos baseados em árvores PQR superaram o método BC e o método MEDIAN, com relação à redução de cruzamentos, em 42% dos casos, empatando nesse critério em 45% dos grafos analisados. Além disso, os métodos baseados em árvores PQR também executaram em um tempo viável para aplicação em estruturas visuais interativas

Abstract: The use of directed acyclic graphs allows the graphical representation of hierarchical structures, which eases to find patterns and trends during the analysis of these structures. The main approach to automatic design of these graphs divides its vertices in layers so that the edges always...

Abstract: The use of directed acyclic graphs allows the graphical representation of hierarchical structures, which eases to find patterns and trends during the analysis of these structures. The main approach to automatic design of these graphs divides its vertices in layers so that the edges always point toward the same direction. One of the major aesthetic criteria of such visual structures is to avoid, whenever possible, the crossing between the edges, thereby facilitating the understanding of the drawing. The crossing reduction algorithms must also provide this solution in a time less than 0.1 second, allowing its use in interactive visual structures. In this dissertation, was investigated as a data structure known as PQR tree could be used to improve both methods for reducing crossings: BC and MEDIAN. Among the new methods developed, stood out: PQR_BC2 for improvement of BC; PQR_M2 for improving the MEDIAN. The results obtained by applying the methods to packets of graphs widely used in the literature show that the methods based on PQR trees outperformed the BC method and the MEDIAN method, with respect to the crossing reduction, in 42% of cases, tying this criterion in 45% of the graph analyzed. In addition, methods based on PQR trees also performed at a feasible time for application to interactive visual structures