On rectilinear duals for vertex-weighted plane graphs

Let G=(V,E)G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of GG is a partition of a rectangle into |V||V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in EE. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph GG admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a rectilinear cartogram can be constructed in O(nlogn)O(nlogn) time where n=|V|n=|V|.