Topological Coordinates: Numerically Encoding the Underlying Topological Structure of Plane Graphs
Author: Saalfeld, Alan
Source: Cartography and Geographic Information Science, 22 January 2009, vol. 36, no. 1, pp. 105-116(12)
Abstract:A new methodology is presented for the concise numerical encoding of a map's topological structure based on several surprising and beautifully intertwined graph decomposition results due to Walter Schnyder. Not only are Schnyder's methods used to determine new positions for a graph's vertices, a map's topological connectivity information is also simultaneously implicitly stored and recovered by folding information about the edge structure of its embedded line-segment graph into numerical topology-based barycentric coordinates chosen for the graph's vertices. Properties of the alternative geometric realization are explored and shown to permit cartogram construction by systematically altering the topological coordinates to modify the regions' relative areas.
Document Type: Research Article
Publication date: January 22, 2009