  We present VMap, a map-like rectangular space-filling visualization, to
perform vertex-centric graph exploration. Existing visualizations have limited
support for quality optimization among rectangular aspect ratios, vertex-edge
intersection, and data encoding accuracy. To tackle this problem, VMap
integrates three novel components: (1) a desired-aspect-ratio (DAR) rectangular
partitioning algorithm, (2) a two-stage rectangle adjustment algorithm, and (3)
a simulated annealing based heuristic optimizer. First, to generate a
rectangular space-filling layout of an input graph, we subdivide the 2D
embedding of the graph into rectangles with optimization of rectangles' aspect
ratios toward a desired aspect ratio. Second, to route graph edges between
rectangles without vertex-edge occlusion, we devise a two-stage algorithm to
adjust a rectangular layout to insert border space between rectangles. Third,
to produce and arrange rectangles by considering multiple visual criteria, we
design a simulated annealing based heuristic optimization to adjust vertices'
2D embedding to support trade-offs among aspect ratio quality and the encoding
accuracy of vertices' weights and adjacency. We evaluated the effectiveness of
VMap on both synthetic and application datasets. The resulting rectangular
layout has better aspect ratio quality on synthetic data compared with the
existing method for the rectangular partitioning of 2D points. On three
real-world datasets, VMap achieved better encoding accuracy and attained faster
generation speed compared with existing methods on graphs' rectangular layout
generation. We further illustrate the usefulness of VMap for vertex-centric
graph exploration through three case studies on visualizing social networks,
representing academic communities, and displaying geographic information.
