Please use this identifier to cite or link to this item:
Title: Removing node overlapping in graph layout using constrained optimization
Authors: Marriott, K.
Stuckey, P.
Tam, V. 
He, W.
Keywords: Constrained optimization
Disjunctive constraints
Graph layout
Issue Date: 2003
Citation: Marriott, K., Stuckey, P., Tam, V., He, W. (2003). Removing node overlapping in graph layout using constrained optimization. Constraints 8 (2) : 143-171. ScholarBank@NUS Repository.
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 problem as a convex quadratic programming problem, which can then be solved by any quadratic solver. The disadvantage is that, since constraints must be linear, the node overlapping constraints cannot be expressed directly, but must be strengthened to obtain a linear constraint strong enough to ensure no node overlapping. The third and fourth approaches are based on local search methods. The third is an adaptation of the EGENET solver originally designed for solving general constraint satisfaction problems, while the fourth approach is a form of Lagrangian multiplier method, a well-known optimization technique used in operations research. Both the third and fourth method are able to handle the node overlapping constraints directly, and thus may potentially find better solutions. Their disadvantage is that no efficient global optimization methods are available for such problems, and hence we must accept a local minimum. We illustrate all of the above methods on a series of layout adjustment problems.
Source Title: Constraints
ISSN: 13837133
DOI: 10.1023/A:1022371615202
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 18, 2018


checked on Sep 25, 2018

Page view(s)

checked on Jul 27, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.