Relational data can be visualized in a map representation. A plurality of vertices and edges are determined based on a set of data identifying objects (i.e., vertices) and relationships (i.e., edges). The vertices and edges are embedded in a planar graph and a Voronoi diagram is generated based at least the plurality of vertices within a set of bounding-points located at least a distance away from the vertices of the map. A bounding-box is associated with each of the vertices, and a set of points generated along each bounding-box. The Voronoi diagram is generated based on the vertices and the set of points of each bounding-box. Each resulting Voronoi cell associated with a common vertex is merged to form a plurality of common cells (i.e., map). The size of each bounding-box can correlate to the importance of its associated vertex, and the points along the bounding-box can be randomly perturbed.