Force-directed Voronoi-based method for graph drawing in constrained boundaries

摘要

We present an efficient force-directed method for evolving an initial graph layout in order to better visualize it, while at the same time distributing graph vertices so as to make full use of the available drawing space. This results in layouts that adjust themselves to the specified boundaries of the drawing area. Previous works have solely focused on the placement of graph vertices and edges for visualization purposes, working under the assumptions of no area limitations nor boundary constraints. Similar to the process of computing a centroidal Voronoi diagram from a set of points, our algorithm iteratively computes a Voronoi diagram over the set of graph vertices, and attracts them towards the centroids of their corresponding Voronoi cells at each iteration. At the same time, attractive and repulsive forces are applied between adjacent vertices in the graph, in order to place them closer to each other in the final layout. Additional consideration is given in order to prevent overlapping in graphs with multiple components.