On Rectilinear Duals for Vertex-Weighted Plane Graphs

De Berg, Mark and Mumford, Elena and Speckmann, Bettina (2006) On Rectilinear Duals for Vertex-Weighted Plane Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 61-72(Official URL: http://dx.doi.org/10.1007/11618058_6).

Full text not available from this repository.


Let G = (V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |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 E. 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 G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_6
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/680

Actions (login required)

View Item View Item