SCIENCE@home

GMap: Drawing Graphs as Maps

E. Gansner,Yifan Hu,S. Kobourov

Published 2009 in International Symposium Graph Drawing and Network Visualization

ABSTRACT

The first step in our GMap algorithm is to embed the graph in the plane. In our implementation we use a scalable force directed algorithm [3]. The second step is a cluster analysis of the underlying graph or the embedded pointset. Here we use modularity based clustering [4] as it is a good fit [5] for the force directed algorithm we employ. In the third step the embedding and the clustering are used to create the map. A Voronoi diagram of the vertices is generated. To create “European-style” borders we use the vertex sets in each cluster together with some random points and generate “form fitting” outer boundaries. Vertex weights are used to determine the font size of the vertex label, and the size of the label is used to create the area in the map that corresponds to the vertex. We then merge Vononoi cells that belong to the same cluster, thus forming regions of complicated shapes. The overall algorithm has complexity O(|V | log|V | )a nd easily scales to graphs with tens of thousands of vertices. Because countries in GMap are not necessarily contiguous, we need as many colors as the total number of countries, in order to make each country uniquely identifiable by its color. We use a two-step heuristic color assignment algorithm to ensure that neighboring countries are colored with as distinctive colors as possible. In the first step we apply a spectral algorithm to the country graph that

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-24 of 24 references · Page 1 of 1

CITED BY

Showing 1-33 of 33 citing papers · Page 1 of 1