Advanced search
Start date

A study of combinatorial optimization problems related to data visualization

Grant number: 12/00673-2
Support type:Scholarships in Brazil - Doctorate (Direct)
Effective date (Start): April 01, 2012
Effective date (End): August 04, 2016
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Cid Carvalho de Souza
Grantee:Rafael Ghussn Cano
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):13/23571-3 - Optimization algorithms for GeoVisualization, BE.EP.DD


The process of decision making, in the context of operations research, consists of analyzing data that is relevant for the considered application. Frequently, visualizing data in maps and diagrams significantly increases the effectiveness of this process and can be of great help for managers. The necessity of automatically producing such visualizations gives rise to several computationally hard combinatorial optimization problems. In this document, we describe two problems related to this topic. In one of them, events are represented by opaque symbols, which might overlap. The goal is to determine the order in which they must be drawn so that the loss of information due to overlap is minimized. The other problem is related to the selection and placement of labels on interactive maps, in which the user is allowed to change the scale or the rotation angle. As the user executes one of these operations, the labels are expected to maintain their size and orientation on the screen. They must be placed in such a way that no two labels overlap in any scale or rotation angle. The objective of this project is to study methods to obtain optimal or near optimal solutions for these and, possibly, other similar problems. Exact algorithms will be developed using integer linear programming, while heuristics will be used to find high quality solutions quickly. The algorithms will be evaluated through several experiments with real world instances. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J. Solving dynamic labeling problems to optimality using solution space reductions. THEORETICAL COMPUTER SCIENCE, v. 789, n. SI, p. 77-92, OCT 15 2019. Web of Science Citations: 0.
CANO, RAFAEL G.; DE SOUZA, CID C.; DE REZENDE, PEDRO J.; YUNES, TALLYS. Arc-based integer programming formulations for three variants of proportional symbol maps. DISCRETE OPTIMIZATION, v. 18, p. 87-110, NOV 2015. Web of Science Citations: 1.
CANO, R. G.; BUCHIN, K.; CASTERMANS, T.; PIETERSE, A.; SONKE, W.; SPECKMANN, B. Mosaic Drawings and Cartograms. COMPUTER GRAPHICS FORUM, v. 34, n. 3, p. 361-370, JUN 2015. Web of Science Citations: 9.
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
. Problemas de otimização combinatória em visualização de dados cartográficos. 2016. 99 f. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação.

Please report errors in scientific publications list by writing to: