In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons and edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight of the corresponding vertex. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine the representation into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal rectangular layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs.
@cite_33: 
@cite_8: T HE idea of the statistical cartogram occurred to the author when he had occasion to prepare maps of the United States showing the distribution of various economic units, such as steel factories, textile mills, power plants, banks, etc. These maps were far too crowded in the northeast to be useful, while elsewhere, for the most part, they were relatively empty. If a way could be found to increase the scale of the northeastern region and reduce that of the west, distribution could be shown more clearly. Simple distortion of the map would be misleading, but, if we go a step farther, discard altogether the outlines of the country, and give each region a rectangular form of size proportional to the value represented, we arrive at the rectangular statistical cartogram. For purposes of comparison it is essential that a definite system of construction should be followed and identical arrangement should be used whatever values are represented. The system here used starts always with the larger divisions and by "proportionate halving" arrives at the smaller ones. It should be emphasized that the statistical cartogram is not a map. Although it has roughly the proportions of the country and retains as far as possible the relative locations of the various regions, the cartogram is purely a geometrical design to visualize certain statistical facts and to work out certain problems of distribution. Examples of these cartograms are given in the accompanying figures. The division into regions follows the usage of the United States Census Bureau, because only from this source are data available. If natural geographic regions could be used instead, the cartograms would be still more instructive.
@cite_9: The topics discussed are minimization of the area occupied by a layout and related results concerning networks flow and rectilinear representation of planar graphs, based on a graph model of floorplans and layouts. Arbitrary floorplans are allowed. Given an arbitrary floorplan and the areas of the embedded building blocks, the existence and uniqueness of a zero wasted area layout are proved, and characterized by a necessary and sufficient condition. Based on this condition, a scheme is described to generate zero-wasted-area layouts. Given a family of dual network pairs for which the product of dual arc lengths are invariant, it is proved that the minimal product of their longest paths is not smaller than the maximal product of their shortest paths. It is also shown that the maximal product of the flows in such a family of dual network pairs is given by the total sum of the arc length product of each individual pair of dual arcs. An efficient procedure to derive a rectilinear representation for any planar graph is presented. >
@cite_0: In many application domains, data is collected and referenced by its geospatial location. Nowadays, different kinds of maps are used to emphasize the spatial distribution of one or more geospatial attributes. The nature of geospatial statistical data is the highly nonuniform distribution in the real world data sets. This has several impacts on the resulting map visualizations. Classical area maps tend to highlight patterns in large areas, which may, however, be of low importance. Cartographers and geographers used cartograms or value-by-area maps to address this problem long before computers were available. Although many automatic techniques have been developed, most of the value-by-area cartograms are generated manually via human interaction. In this paper, we propose a novel visualization technique for geospatial data sets called RecMap. Our technique approximates a rectangular partition of the (rectangular) display area into a number of map regions preserving important geospatial constraints. It is a fully automatic technique with explicit user control over all exploration constraints within the exploration process. Experiments show that our technique produces visualizations of geospatial data sets, which enhance the discovery of global and local correlations, and demonstrate its performance in a variety of applications
@cite_16: A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good rectangular cartograms are hard to generate: The area specifications for each rectangle may make it impossible to realize correct adjacencies between the regions and so hamper the intuitive understanding of the map. We present the first algorithms for rectangular cartogram construction. Our algorithms depend on a precise formalization of region adjacencies and build upon existing VLSI layout algorithms. Furthermore, we characterize a non-trivial class of rectangular subdivisions for which exact cartograms can be computed efficiently. An implementation of our algorithms and various tests show that in practice, visually pleasing rectangular cartograms with small cartographic error can be generated effectively.
In the above results on rectilinear duals and rectangular duals, the areas of the polygons are not considered; that is, these results deal with the unweighted version of the problem. The weighted version dates back to 1934 when Raisz described rectangular cartograms @cite_8 . Algorithms by van Kreveld and Speckmann @cite_16 and Heilmann @cite_0 yield representations with touching rectangles but the adjacencies may be disturbed and there may also be a small distortions of the weights. Recently, Eppstein @cite_33 characterized the class of planar graphs that have area-universal rectangular duals. The construction of the actual cartogram, given the area-universal rectilinear dual and the weight function, can be accomplished using a result by Wimer @cite_9 , which in turn requires numerical iteration.