Desenvolvimento de novas metodologias para desenho automático de grafos baseadas em otimização

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.