Drawing Graphs for Cartographic Applications (PDF
Graphs are ubiquitous in computer science, and visualizing them in a good way has become the topic of the research area known as graph drawing. It combines techniques from graph theory, algorithms, (computational) geometry, and (computational) topology, and has applications to cartography, VLSI design, and information visualization, among others. This thesis studies three graph drawing problems. The first problem is the construction of rectilinear cartograms, where each region on a map is deformed into a rectilinear polygon whose area represents some value associated with the area (say, the population of a country). The resulting cartogram should resemble the original map as closely as possible in terms of shapes and adjacencies of the regions, while at the same time faithfully representing the value associated with each region. The second problem concerns cased drawings of graphs, where edge crossings are drawn in a way that suggests that one edge goes underneath the other. The third problem is to decide for certain curves and surfaces whether they could occur as the boundary of some shape.