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, Limerick, Ireland , pp. 61-72 (Official URL: http://dx.doi.org/10.1007/11618058_6).

Full text not available from this repository.

Abstract

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
ID Code:680

Repository Staff Only: item control page

References

J. Bhasker and S. Sahni.: A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks, 7:307--317, 1987.

T. Biedl and B. Genc.: Complexity of octagonal and rectangular cartograms. Proceedings of the 17th Canadian Conference on Computational Geometry, pages 117--120, 2005.

F. d'Amore and P. G. Franciosa.: On the optimal binary plane partition for sets of isothetic rectangles. Information Processing Letters, 44(5):255--259, 1992.

B. Dent.: Cartography - thematic map design. McGraw-Hill, 5th edition, 1999.

J. A. Dougenik, N. R. Chrisman, and D. R. Niemeyer.: An algorithm to construct continous area cartograms. Professional Geographer, 37:75--81, 1985.

R. Heilmann, D. A. Keim, C. Panse, and M. Sips.: Recmap: Rectangular map approximations. Proceedings of the IEEE Symposium on Information Visualization (INFOVIS), pages 33--40, 2004.

G. Kant and X. He.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172:175--193, 1997.

K. Kozminski and E.Kinnen.: Rectangular dual of planar graphs. Networks, 5:145--157, 1985.

C. C. Liao, H. I. Lu, and H. C. Yen.: Floor-planning using orderly spanning trees. Journal of Algorithms, 48:441--451, 2003.

NCGIA / USGS.:Cartogram Central, 2002. http://www.ncgia.ucsb.edu/projects/Cartogram_Central/index.html.

M. S. Rahman, K. Miura, and T. Nishizeki.: Octagonal drawings of plane graphs with prescribed face areas. Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 3353 in LNCS, pages 320--331. Springer, 2004.

E. Raisz.: The rectangular statistical cartogram. Geographical Review, 24:292--296, 1934.

C. Thomassen.: Plane cubic graphs with prescribed face areas.Combinatorics, Probability and Computing, 1:371--381, 1992.

M. van Kreveld and B. Speckmann.: On rectangular cartograms. Computational Geometry: Theory and Applications, 2005. To appear.

G. K. Yeap and M. Sarrafzadeh.: Sliceable floorplanning by graph dualization. SIAM Journal of Discrete Mathematics, 8(2):258--280, 1995.