Removing node overlapping in graph layout using constrained optimization

Abstract

Although graph drawing has been extensively studied, little attention has been paid to the problem of node overlapping. The problem arises because almost all existing graph layout algorithms assume that nodes are points. In practice, however, nodes may be labelled, and these labels may overlap. Here we investigate how such node overlapping can be removed in a subsequent layout adjustment phase. We propose four different approaches for removing node overlapping, all of which are based on constrained optimization techniques. The first is the simplest. It performs the minimal linear scaling which will remove node-overlapping. The second approach relies on formulating the node overlapping proble..