Acartogram is one of the most powerful visualization tools for spatial data in quantitative geography (e.g. Monmonier 1977; Dorling 1996; Tobler 2004). An area cartogram, one of the most familiar cartograms, is a transformed map on which the areas of regions are proportional to the data values. Deformation of the shape of regions and their displacements assist map-readers in intuitively recognizing the distribution of data represented on area cartograms. In this study, area cartograms are hereafter referred to as cartograms.
Cartograms are classified on the basis of two characteristics: the shapes and contiguities of regions indicated on the cartograms. For the shapes of regions, some cartograms use complex shapes (e.g. Tobler 1973; 1986; Dougenik et al. 1985; Gusein-Zade and Tikunov 1993; House and Kocmoud 1998; Keim et al. 2004, Gastner and Newman 2004; Inoue and Shimizu 2006), whereas others use simple shapes such as circles and rectangles. The ease of comparison between cartograms with complex shapes of regions and geographical maps enables map-readers to comprehend the characteristics of spatial data presented in such cartograms. However, comparison of cartograms with complex region shapes is difficult in terms of the size of the regions; in this sense, it is better to use simple shapes to express data.
Cartograms that express regions in the form of simple shapes are classified into two types on the basis of contiguities of the regions illustrated on them. One is contiguous cartograms; a rectangular cartogram proposed by Rasiz (1934) serves as an example. Rectangles represent regions, and different rectangles representing adjacent regions are placed contiguously. A rectangular cartogram is an effective visualization tool, as the size of regions is easy to perceive. However, its construction is difficult because it is impossible to maintain all contiguities of regions in many cases; it then becomes necessary to omit some of the contiguities. Therefore, although several solutions have been proposed (e.g. Heilmann et al. 2004; Speckmann et al. 2006; van Kreveld and Speckmann 2007), their applications are limited. The other type is non-contiguous cartograms; rectangular cartograms proposed by Upton (1991) and circle (or circular) cartograms proposed by Dorling (1996) are examples. They represent regions by rectangles and circles and omit the contiguities of regions. In particular, a circle cartogram is often used for visualization because of its simple construction algorithm.
Dorling (1996) first proposed a circle cartogram construction algorithm according to two requirements for an easily comprehensible resultant: 'avoid overlap of circles' and 'keep contiguity of regions as much as possible'. It is also important to 'keep the similarity of configuration between circles on cartograms and regions on geographical maps'; accordingly, the algorithm first places circles according to the geographical configuration of regions and then moves circles one by one in order to fulfill the requirements. The algorithm outputs results that express a spatial distribution of data, and that are widely used (e.g. Anselin et al. 2006; Herzog 2010). However, the relative positions of circles on cartograms sometimes differ greatly from the geographical maps; the displacement of circles then causes difficulty- in distinguishing which circles represent which regions.
There are two shortcomings with the previous algorithm. One is that the algorithm does not consider maintaining the relative position of circles explicitly. The information on region contiguity, includes information on the relative position of regions; however, this is not sufficient to keep the similarity of positions between circles on cartograms and the positions of corresponding regions on maps. The other shortcoming is that the previous algorithm moves circles one by one to search for a circle configuration that satisfies the requirements for circle cartogram construction. …