  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.
