Orientadores: Cid Carvalho de Souza, Pedro Jussieu de RezendeTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Conjuntos de dados podem ser representados de muitas maneiras. Tabelas são, provavelmente, a forma mais simples de apresentação e mostram-se úteis quando se deseja consultar valores associados a objetos específicos. No entanto, se o objetivo é identificar relações entre diferentes objetos, outras formas de representação podem ser mais adequadas. Para este fim, uma visualização em forma esquemática através de imagens e diagramas pode, frequentemente, revelar novos aspectos dos dados. Isto ocorre especialmente em se tratando de dados cartográficos, isto é, dados associados a regiões ou localizações geográficas. Nestes casos, visualizações apropriadas podem evidenciar relações e padrões espaciais anteriormente desconhecidos, possibilitando uma análise mais aprofundada dos fenômenos observados. A construção manual de mapas necessita de cartógrafos experientes e consome muito tempo. Portanto, é interessante o desenvolvimento de algoritmos que permitam a automação desta tarefa. Cada tipo de visualização apresenta restrições e métricas de qualidade específicas. Originam-se, então, diversos problemas de otimização combinatória, os quais são, com frequência, computacionalmente difíceis. Esta tese propõe-se a estudar alguns destes problemas. Foram considerados quatro tipos de visualização para dados cartográficos: mapas de símbolos proporcionais, mapas rotacionáveis, cartogramas em mosaicos e cartogramas retangulares. Mapas de símbolos proporcionais representam dados através de símbolos opacos, que podem se sobrepor. O problema abordado consiste em determinar a ordem na qual os símbolos devem ser desenhados de forma a maximizar sua visibilidade de acordo com métricas estabelecidas na literatura. Nossas contribuições incluem um novo modelo de programação linear inteira e uma análise poliédrica do mesmo, um algoritmo de branch-and-cut com rotinas eficientes de separação de desigualdades e procedimentos de lifting. Mapas rotacionáveis são mapas que permitem ao usuário executar rotações. Nosso estudo teve como objetivo encontrar soluções ótimas para um problema de rotulação. Como em problemas tradicionais, deseja-se colocar rótulos textuais no mapa sem que ocorram sobreposições. Porém, conforme o mapa é rotacionado, todos os rótulos devem permanecer alinhados na direção horizontal, o que pode causar o surgimento de novos conflitos. Em nosso trabalho, provamos várias propriedades de soluções ótimas e mostramos como reduzir em centenas de vezes o número de variáveis e restrições de um modelo de programação linear inteira da literatura. Finalmente, cartogramas são mapas usados para representar dados estatísticos sobre regiões (e.g., estados ou países). Cada região tem seu tamanho alterado de forma que sua área seja proporcional ao dado que se deseja retratar. Nós propomos o primeiro algoritmo para construção de cartogramas em mosaicos. Além disso, expandimos um método existente de construção de cartogramas retangulares com uma heurística que cria as chamadas regiões de marAbstract: Data can be represented in various ways. Tables are likely to be the simplest form of presenting it. Still, they are useful when it is necessary to retrieve data values associated with specific objects. However, if one is interested in identifying relations between different objects, other forms of representation might be more suitable. To that end, a schematic visualization in images and diagrams can often reveal new aspects of the data. This is true especially for cartographic data, i.e., data that is associated with locations or regions of a map. In these cases, appropriate visualizations can exhibit spatial patterns and relations that were previously unknown, enabling a deeper analysis of the observed phenomena. Manually constructing maps requires experienced cartographers and is extremely time-consuming. Therefore, there is a need for algorithms to automate this task. Each type of visualization has specific constraints and quality metrics. These give rise to several combinatorial optimization problems, which are, frequently, computationally hard. This thesis aims at studying some of these problems. We consider four types of visualizations for cartographic data: proportional symbol maps, rotating maps, mosaic cartograms and rectangular cartograms. Proportional symbol maps represent data through opaque symbols, that might overlap. The problem we address consists in determining the order in which the symbols must be drawn, such that their visibility is maximized according to established metrics. Our contributions include a novel integer linear programming model and an analysis of the associated polytope, a branch-and-cut algorithm with fast separation routines, and lifting procedures. Rotating maps are maps that allow the user to rotate the view. The goal of our study was to find optimal solutions to a labeling problem. Just as in classic problems, labels must be placed on the map without overlap. However, as the map is rotated, all labels must remain horizontally aligned, and this may cause new conflicts to arise. In our work, we prove several properties of optimal solutions and show how to reduce the number of variables and constraints of an existing integer programming model by up to two orders of magnitude. Finally, cartograms are maps used to depict statistical data about regions (e.g., states or countries). Each region is scaled in such a way that its area becomes proportional to the associated numerical value. We propose the first algorithm for the construction of mosaic cartograms. In addition, we extend an existing method to build rectangular cartograms with a heuristic that creates so-called sea regionsDoutoradoCiência da ComputaçãoDoutor em Ciência da Computação2012/00673-2FAPESP