We study contact representations of graphs in the plane and in 3D space, where vertices are represented by polygons or polyhedra and each edge is represented by a common boundary between two polygons or polyhedra. In the weighted version of the problem, we find contact representations with the additional restriction that the areas for the polygons or the volumes for the polyhedra realize some pre-specified value for the vertices. We address different variants of the problem depending on the types of polygons or polyhedra (convex or non-convex, axis-aligned or not), types of contacts (proper contacts with common boundaries of non-zero lengths in 2D or non-zero areas in 3D or improper contacts where common boundaries of zero lengths or areas are allowed), and whether holes are allowed in the representation or not. In the plane we mainly focus on the weighted version of the problem. We find optimal (in terms of polygonal complexity) contact representations for planar graphs (both for axis-aligned and non-axis-aligned polygons) and some subclasses of planar graphs. With non-axis-aligned polygons we show that non-convex polygons with 4 sides are sometimes necessary and always sufficient for proportional contact representation of a planar graph, when point contacts are allowed; otherwise for proper contacts 7-sided polygons are sometimes necessary and always sufficient. We give a linear-time algorithm in each case to compute the optimal representation. We also give quadratic-time algorithms to construct optimal proportional contact representations for (2, 0)-sparse graphs (with triangles for improper contacts and with convex quadrilaterals for proper contacts). For maximal outerplanar graphs proportional contact representation with triangles can also be computed in linear time. In case only axis-aligned polygons are used, we show that 8 sides are sometimes necessary and always sufficient for a planar graph. While we do not have a polynomial-time algorithm to construct such a representation, we give a linear-time algorithm to compute representation with 10-sided axis-aligned polygons. We also give linear-time construction algorithms for optimal proportional contact representations with 8-sided polygons for planar 3-trees and Hamiltonian maximal planar graphs, and with rectangles for maximal outerplanar graphs. For contact representation with 3D polyhedra, we consider both the weighted and the unweighted variants of the problem for both planar and non-planar graphs and have some preliminary results. We find several subclasses of planar graphs that have contact representations using cubes or proportional boxes. We also consider (improper) contact representations using tetrahedra, and show that planar graphs, complete bipartite and tripartite graphs, and complete graphs with at most 10 vertices have contact representations with tetrahedra. We also addressed variants of this problem using only unit regular tetrahedra or considering contacts only between apices of the tetrahedra or using both restrictions.

Cartograms are value-by-area maps which modify geographic regions, such as countries, in proportion to some variable of interest, such as population. These are popular georeferenced data visualizations that have been used for over a century to illustrate patterns and trends in the world around us. A wide variety of cartogram types exist, that were designed to optimize different cartogram dimensions, such as geographic accuracy and statistical accuracy. This work surveys cartogram research in visualization, cartography and geometry, covering a broad spectrum of different cartogram types: from the traditional rectangular cartograms, to Dorling and diffusion cartograms. Based on prior work in visualization and cartography, I propose a task taxonomy of cartograms, and describe a study of cartograms based on quantitative metric-based comparisons, task-based time-and-error evaluation, and subjective preference and feedback analysis. For these evaluations, I considered four major types of cartograms which allowed us to compare and analyze the evaluation strategies and discuss the implications of the surprising outcomes. In the context of maps, the ability to recall information shown in the map is one of the important factors in determining effectiveness. In spite of some early studies that involved cartograms, the memorability of different cartogram types has not been investigated. In order to create effective data presentations, we first need to understand what makes a visualization memorable. I investigate the memorability of contiguous and Dorling cartograms, both in terms of recognition of the map and recall of data. Finally, I describe bivariate cartograms, a technique specifically designed to allow for the simultaneous comparison of two geo-statistical variables. Traditional cartograms are designed to show only a single statistical variable, but in practice, it is often useful to show two variables (e.g., the total sales for two competing companies) simultaneously. Bivariate cartograms make it easy to find geographic patterns and outliers in a pre-attentive way. They are most effective for showing two variables from the same domain (e.g., population in two different years, sales for two different companies), although they can also be used for variables from different domains (e.g., population and income). I also describe a small-scale evaluation of the proposed techniques that indicates bivariate cartograms are especially effective for finding geo-statistical patterns, trends and outliers.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第21318号 / 情博第675号 / 新制||情||117(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 山本 章博, 教授 山下 信雄, 教授 田中 利幸, 上田 修功 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM