Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/RCMA-8EEN5Z
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Renato Cardoso Mesquita | pt_BR |
dc.contributor.advisor-co1 | Frederico Gadelha Guimaraes | pt_BR |
dc.contributor.referee1 | Petr Iakovlevitch Ekel | pt_BR |
dc.contributor.referee2 | Marcone Jamilson Freitas Souza | pt_BR |
dc.contributor.referee3 | Oriane Magela Neto | pt_BR |
dc.contributor.referee4 | Hugo Alexandre Dantas do Nascimento | pt_BR |
dc.creator | Bernadete Maria de Mendonca Neta | pt_BR |
dc.date.accessioned | 2019-08-10T16:11:17Z | - |
dc.date.available | 2019-08-10T16:11:17Z | - |
dc.date.issued | 2010-12-22 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/RCMA-8EEN5Z | - |
dc.description.abstract | The general goal of this work is the study and development of methodologies for automatic graph drawings in order to assist the solution of important problems related to the quality, readability, reliability and visibility of information provided by applications that use resources related to the visual representation of data. Typically these applications have characteristics very demanding in terms of aesthetic criteria, constraints and mainly efficiency, given that they often require real time decision making. To achieve this goal, the approach for orthogonal graph drawings called topology-shape-metric has been studied. This approach consists in treating the drawing in three steps: planarization, orthogonalization and compaction. Given that each step represents an NP-hard problem, each step is handled by heuristics that aim at resolving certain aesthetic criteria. Most often these aesthetic criteria conflict with each other. Since we have several aesthetic criteria that must be treated, one can clearly deal with them using multicriteria optimization techniques. This approach has some opened problems that will be solved in this work. This work presents the following contributions: i) mathematical models that represent different aesthetic criteria and its solution by integer linear programming (ILP) and multicriteria optimization techniques in the compaction step are obtained; ii) three hybrid approaches considering the topology-shape-metrics and genetic algorithm are developed and iii) a unified methodology for obtaining orthogonal graph drawings on the grid is developed. This is related to a new methodology, considered unified because it solves, simultaneously, the aesthetic criteria: crossings minimization, bends minimization and the total sum of the edges length minimization with genetic algorithm and local search algorithms. The methodology for ILP showed better results than the approach of minimum cost flow in the network when applied considering only one aesthetic criterion in compaction step. When used in context with the variety of goals modeled, showed interesting results. The hybrid approaches solved the problem of fixing the planar embedding in the topology-shape-metric and showed improvements of approximately 50% compared to the classical approach results, for the worst case treated. Moreover, it ensures flexibility to address the number of aesthetic criteria and constraints necessary. It is independent of the mathematical model characteristics that represent them, since it works in conjunction with the genetic algorithm. | pt_BR |
dc.description.resumo | Este trabalho tem como objetivo geral o estudo e desenvolvimento de novas metodologias para desenho automático de grafos. Estas visam auxiliar na resolução de importantes problemas relacionados com a qualidade, legibilidade, confiabilidade e visibilidade das informações providas por aplicativos que utilizam recursos relacionados com a representação visual de dados. Normalmente estes aplicativos possuem características bastante exigentes em termos de critérios estéticos, restrições de desenho e principalmente eficiência, uma vez que exigem tomadas de decisões, na maioria das vezes, em tempo real. Para se atingir este objetivo, a abordagem para desenho de grafos ortogonais, denominada topologia-forma-métrica, foi estudada. Esta abordagem consiste em tratar o desenho em três etapas: planarização, ortogonalização e compactação. Por se tratar de um problema NP-Difícil, cada etapa é resolvida por heurísticas que visam atender a determinados critérios estéticos. Na maioria das vezes, estes critérios estéticos conflitam entre si, o que mostra tratar-se de um problema de otimização. Como são vários os critérios estéticos a serem considerados, pode-se claramente utilizar técnicas de otimização multicritério. Esta abordagem possui os seguintes problemas em aberto: i) não permitir o tratamento de mais de um critério estético por etapa; ii) fixar o embutimento planar que será submetido as próximas etapas. Isto não garante um desenho otimizado ao final do processo; ii) existência de dependências entre as três etapas da abordagem, exigindo que elas sejam executadas em uma ordem pré-definida. Estes problemas serão solucionados neste trabalho. As principais contribuições do trabalho são: i) a obtenção dos modelos matemáticos que representam diversos critérios estéticos e o tratamento dos mesmos por técnicas de programação linear inteira (PLI) e otimização multicritério na etapa de compactação; ii) o desenvolvimento de três abordagens híbridas utilizando a topología-forma-métrica com o algoritmo genético, e iii) o desenvolvimento de uma metodologia unificada que trabalha simultaneamente com os critérios de minimização de cruzamentos, dobras e a soma total das arestas, com o auxílio do algoritmo genético e de operadores de busca local. A metodologia por PLI gerou resultados melhores que a abordagem do fluxo de custo mínimo em rede quando aplicada considerando apenas um critério estético na compactação. Quando utilizada em um contexto com os vários objetivos modelados, gerou bons resultados respeitando os critérios estéticos e suas restrições. As abordagens híbridas resolveram o problema de fixar o embutimento planar existente na topologia-forma-métrica e apresentou melhorias de aproximadamente 50%, quando comparada aos resultados da abordagem clássica, para o pior caso tratado. A abordagem unificada, além de eliminar a interdependência entre as etapas, conforme ocorre na topologia-forma-métrica, apresentou bons resultados para a solução de problemas de desenhos ortogonais no grid. Além disto, ela garante flexibilidade para o tratamento do número de critérios estéticos e restrições necessárias e independe das características do modelo matemático que os representam, uma vez que trabalha em conjunto com o algoritmo genético. | pt_BR |
dc.language | Português | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Engenharia Elétrica | pt_BR |
dc.subject.other | Engenharia elétrica | pt_BR |
dc.title | Desenvolvimento de novas metodologias para desenho automático de grafos baseadas em otimização | pt_BR |
dc.type | Tese de Doutorado | pt_BR |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis_berna_v1.14_final.pdf | 3.05 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.