Labeled Graph Drawing based on the Individual Ellipsoidal Potentials

Matsubayashi Tatsushi, Yamada Takeshi, Fujimura Shigeru, Fujimura Ko

We present a new graph layout algorithm for a graph with node labels. The proposed algorithm can generate a graph layout efficiently avoiding overlapping of node labels. Most of the conventional algorithms such as force-directed and spring methods compute node positions by treating nodes as "points", and thus may cause node overlapping when strings or labels with various sizes are added to the nodes. Most of the conventional approaches to solve this problem require an initial graph layout generation phase without considering label sizes and a separate overlap removal phase as its post processing. These methods are not suitable for a large-scale graph layout, because their computational costs are high and they may even destroy the initial graph layout. The proposed algorithm gives an individually different ellipsoidal potential to each node depending on its label size as well as a common point-symmetric potential, and the combination of these two potentials defines the repulsion force. This enables an efficient graph layout that can avoid local node overlaps while maintaining the global structure. By implementing it on the GPU, the proposed algorithm can compute high quality layouts of large-scale graphs in some hundredths fraction of time required by the conventional algorithms.

Labeled Graph Drawing based on the Individual Ellipsoidal Potentials

Bibliographic Information

Search this article

Description

Journal

Details 詳細情報について

Export

Report a problem