Desenho de grafos: uma abordagem utilizando programação linear inteira

Abstract

An important problem in data visualization is the information organization into structures that show entities and their relationships. This problem can be more complex as the number of entities increases. The way a graph is drawn can directly impact on the information quality and reliability. For large amount of data, or, when large number of aesthetic requirements had to be defined, the automatic graph drawing problem becomes a very relevant problem. The methodology study and the development of a computational tool designed to build automatic graph drawing are the objectives of this work, optimizing the graph data visual complexity, readability and many kinds of aesthetic requirements. To achieve these goals, the Integer Linear Programming (ILP) approach was used in algorithm steps, just for treating electric circuits drawing requirements in an efficient way. Two approaches are presented: the topology-metric-shape deals the drawing in three steps: planarization, responsible for the definition of a planar embedding; orthogonalization, responsible for vertices and edges angles definition; and the compaction, which defines the compact drawing coordinates. Another approach, the hierarchical one, targets a drawing in levels, and achieves better results in some kinds of graph drawing problems, like flow schemas in electric power systems diagrams. Graph drawings built with the different approaches are largely discussed and compared. The obtained results show that the ILP approach allows the insertion of requirements in the system in a simple way. This enables the insertion of many aesthetic requirements.